45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04) Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique Rome, Italy October 17-October 19 ISBN: 0-7695-2228-9
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.59
Assuming that NP ⊈ ∩_ε > 0 BPTIME(2^n^ε), we show that GraphMin-Bisection, Densest Subgraph and Bipartite Clique have no PTAS. We give a reduction from the Minimum Distance of Code Problem (MDC). Starting with an instance of MDC, we build a Quasi-random PCP that suffices to prove the desired inapproximability results. In a Quasi-random PCP, the query pattern of the verifier looks random in some precise sense. Among the several new techniques introduced, we give a way of certifying that a given polynomial belongs to a given subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial and it can be checked by reading a constant number of its values.
Citation:
Subhash Khot, "Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique," focs, pp.136-145, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb