Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique

Research output: Contribution to journalArticlepeer-review

Abstract

Assuming that NP ⊈ ∩ε > 0 BPTIME(2 ), we show that graph min-bisection, dense fc-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.

Original languageEnglish (US)
Pages (from-to)1025-1071
Number of pages47
JournalSIAM Journal on Computing
Volume36
Issue number4
DOIs
StatePublished - 2006

Keywords

  • Approximation algorithms
  • Hardness of approximation
  • Probabilistically checkable proofs (PCPs)

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique'. Together they form a unique fingerprint.

Cite this