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.