enter search term and/or author name
Fast and accurate algorithms for protein side-chain packing
Jinbo Xu, Bonnie Berger
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
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
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
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...