Ruling Out PTAS for Graph Min-Bisection

COMPUTER SCIENCE/DISCRETE MATH SEMINAR II
Topic:Ruling Out PTAS for Graph Min-Bisection
Speaker:Subhash Khot
Affiliation:IAS
Date:Tuesday, June 1
Time/Room:10:30am - 12:30pm/S-101

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(log2 n) approximation algorithm for this problem. On the other hand, no inappro- ximability 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+\eps)-approximation algorithm for every \eps > 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.