Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 53 Issue 4, July 2006

Fast and accurate algorithms for protein side-chain packing
Jinbo Xu, Bonnie Berger
Pages: 533-557
DOI: 10.1145/1162349.1162350
This article studies the protein side-chain packing problem using the tree-decomposition of a protein structure. To obtain fast and accurate protein side-chain packing, protein structures are modeled using a geometric neighborhood graph, which can be...

Locally testable codes and PCPs of almost-linear length
Oded Goldreich, Madhu Sudan
Pages: 558-655
DOI: 10.1145/1162349.1162351
We initiate a systematic study of locally testable codes; that is, error-correcting codes that admit very efficient membership tests. Specifically, these are codes accompanied with tests that make a constant number of (random) queries into any given...

Distribution sort with randomized cycling
Jeffrey Scott Vitter, David Alexander Hutchinson
Pages: 656-680
DOI: 10.1145/1162349.1162352
Parallel independent disks can enhance the performance of external memory (EM) algorithms, but the programming task is often difficult. Each disk can service only one read or write request at a time; the challenge is to keep the disks as busy as...

Backing up in singly linked lists
Amir M. Ben-Amram, Holger Petersen
Pages: 681-705
DOI: 10.1145/1162349.1162353
We show how to reduce the time overhead for implementing two-way movement on a singly linked list to O(nε) per operation without modifying the list and without making use of storage other than a finite number of pointers...