Back to Search
Start Over
RULING OUT PTAS FOR GRAPH MIN-BISECTION, DENSE k-SUBGRAPH, AND BIPARTITE CLIQUE.
- Source :
-
SIAM Journal on Computing . 2006, Vol. 36 Issue 4, p1025-1071. 47p. 1 Illustration, 2 Diagrams. - Publication Year :
- 2006
-
Abstract
- Assuming that NP ⊈ ∩ϵ>0 BPTIME(2nϵ), we show that graph min-bisection, dense k-subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We give a reduction from the minimum distance of code (MDC) problem. Starting with an instance of MDC, we build a quasi-random probabilistically checkable proof (PCP) that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in a certain precise sense. Among the several new techniques we introduce, the most interesting one gives a way of certifying that a given polynomial belongs to a given linear subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial, and it can be checked probabilistically by reading a constant number of its values. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 36
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 24844826
- Full Text :
- https://doi.org/10.1137/S0097539705447037