## Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing: El Paso, Texas, May 4-6, 1997 |

### What people are saying - Write a review

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

### Contents

Sunday May | 1 |

A Complete Classification of the Approximability of Maximization Problems Derived from Boolean | 11 |

The Approximability of Geometric TSP and | 21 |

Copyright | |

65 other sections not shown

### Common terms and phrases

Alice and Bob approximation algorithm assignment assume Boolean chain circuit codes commitment scheme communication complexity competitive ratio Computer Science connected components consider constant constraint construction contains corresponding cost database decoding defined definition degree denote distribution Erdös Erdös's error evaluation exists floor-plan flow function given Goldreich gorithm graph G IEEE implies input instance integer k-connected k-connected graph least Lemma length linear linear code lower bound machines matching matrix node NP-complete NP-hard O(log Oblivious Oblivious Transfer obtained on-line online algorithm optimal output parameter path permutation planar graph points polynomial probabilistic probability problem Proc processors proof protocol prove quantum qubits queries random bits randomized algorithm result rithm satisfies schedule ſee separating triangles sequence servers solution startnode step STOC subset subtree Theorem Theory tion transform tree upper bound variables vector vertex vertices