Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique

Research output: Contribution to journalConference articlepeer-review

Abstract

Assuming that NP ⊄ ∩ ε>0 BPTIME(2 ), we show that Graph Min-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.

Original languageEnglish (US)
Pages (from-to)136-145
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - 2004
EventProceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 - Rome, Italy
Duration: Oct 17 2004Oct 19 2004

ASJC Scopus subject areas

  • Engineering(all)

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

Cite this