What people are saying - Write a review
We haven't found any reviews in the usual places.
A Complete Classification of the Approximability of Maximization Problems Derived from Boolean
The Approximability of Geometric TSP and
65 other sections not shown
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