## Foundations of Computer Science: Proceedings of the Annual Symposium, New York, 1999The 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 nČLower Bound for the Rank of nxnMatrix Multiplication over Arbitrary Fields 2 | 50 |

Copyright | |

1 other sections not shown

### Other editions - View all

### Common terms and phrases

algorithm allocation apply approximation assignment assume balls bits block cache circuit claim complexity Computer consider constant construction contains corresponding cost defined definition denote described distance distribution dynamic edge elements error example exists facility fact factor Figure Finally flow function give given graph Hence holds implies independent input instance integer known label least Lemma length linear lower bound machine matrix maximum merge metric min-entropy move node Note obtain operations optimal output pair path perform players polynomial positive possible present probability problem proof protocol prove quantum queries random respect result running satisfies schedule scheme Science sequence solution space step structure takes Theorem Theory tion tree variables vertex vertices weight