Computer Science/Discrete Mathematics Seminar II

Graph Min-Bisection is the following problem: Given a graph, partition it into two equal parts so as to minimize the number of crossing edges. The problem arises as a subroutine in many graph algorithms that rely on divide-and-conquer strategy. Feige and Krauthgamer gave an $O(\log^2 n)$ approximation algorithm for this problem. On the other hand, no inapproximability result was known. It was one of the central open questions in (in)approximability theory whether Min-Bisection has a Polynomial Time Approximation Scheme (i.e. $(1+\epsilon)$-approximation algorithm for every $\epsilon > 0$).

The result is this talk resolves the above question, ruling out PTAS for Min-Bisection and two other important problems called Densest Subgraph and Bipartite Clique. Recently, Feige ruled out a PTAS for these problems assuming a certain conjecture about average-case hardness of Random 3SAT. Our result needs only a (standard) assumption that NP has no subexponential time algorithms.

The result follows via a new construction of a PCP where the queries of the verifier "look random". To be precise, the verifier makes $q$ queries and for any set of half the bits in the proof, the probability that all queries fall into this set is essentially $1/2^q$. We introduce several new ideas and techniques, in addition to using variations/generalizations of algebraic techniques used to prove the PCP Theorem. I will try to make the talk as self-contained as possible.