Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique
Subhash Khot · 2004
Assuming that NP /spl nsube//spl cap//sub /spl epsi/> 0/ BPTIME(2/sup n/spl epsi//), 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.