## 40th Annual Symposium on Foundations of Computer Science: October 17-19, 1999, New York City, New YorkThe proceedings consists of the 67 papers presented at the October 1999 symposium. Among the topics are approximation schemes for minimizing average weighted completion time with release dates, improved bounds for sampling colorings, dynamic planar convex hull operations in near-logarithmic amortized time, Markovian coupling vs. conductance for the Jerrum-Sinclair chain, and bounds for small- error and zero-error quantum algorithms. Some other topics are online scheduling to minimize average stretch, algorithmic aspects of protein structure similarity, non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security, stochastic load balancing and related problems, and the testability of regular languages with a constant number of queries. No subject index. Annotation copyrighted by Book News, Inc., Portland, OR. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Approximating Fractional Multicommodity Flow Independent of the Number of Commodities | 24 |

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates | 32 |

A n2Lower Bound for the Rank of nxiMatrix Multiplication over Arbitrary Fields | 45 |

Copyright | |

62 other sections not shown

### Other editions - View all

### Common terms and phrases

allocation apply approximation algorithm assignment assume balls bits cache cache-oblivious algorithm circuit competitive ratio complexity Computer Science consider constant construction contains cost data structure defined definition denote deterministic distance distribution dual dynamic edge elements encryption exists exponential extractor facility factor flow function given gorithm Hence IEEE implies input integer interactive proof systems label least Lemma length linear lower bound machine Markov Markov chain matrix maximum merge metric metric space min-entropy minimal node obtain online algorithm operations optimal oracle output pair parameter permutation players polynomial prob probabilistic probability problem Proc proof systems protocol prove quadtree quantum quantum circuit quantum computation qubits queries random recursive result rithm schedule scheme sequence shortest path simulation solution space step string subgraph subset technique Theorem Theory of Computing tion trapezoid undirected graphs UOWHF upper bound variables vector vertex vertices weight