What people are saying - Write a review
We haven't found any reviews in the usual places.
SDP Gaps and UGC Hardness for Multiway Cut OExtension and Metric Labeling
67 other sections not shown
Other editions - View all
Alice Alice and Bob apply approximation algorithm assume checker ciphertext circuit communication complexity compression Computer Science connectivity consider constant constraint languages construct cost covariance cryptosystem define Definition denote dfvs directed graph disjoint distribution edges efficient encryption execution exists exponential feedback vertex set fixed-parameter tractable formula fraction full version gates given graph G greedy algorithm hard implies inequality injective function input instance integrality gap interactive proof lattice Lemma linear lower bound matrix matroid maximization mechanism min-cut nodes NP-complete NP-hard obtain operation optimal oracle output pair parameter path players polynomial probabilistic probability problem protocol prove PSPACE quantum queries random reduction result round route sampling satisfies Section skew separator solution solving span program STOC subgraph submodular subset Symposium terminals Theory of Computing tion trapdoor functions Unique Games valuation variables vector verifier vertex vertices Wait command