DIMACS Seminar on Theoretical Computer Science


"Reductions, Codes, PCPs, and Inapproximability" (Or, Limitations of Current Techniques for Proving Inapproximability)


Sanjeev Arora
Princeton University


DIMACS Seminar Room, CoRE Building, Room 431
Busch Campus, Rutgers University


10:00 AM
Wednesday, April 26, 1995


Recent results have shown that computing approximate solutions to several NP-hard optimization problems is NP-hard. But it is unclear what the limitations of these techniques are: Which inapproximability results can they not prove?

Our research addresses such questions. We identify a broad class of reductions -- namely, code-like reductions -- that includes all reductions used in known inapproximability results. We prove, under reasonable complexity assumptions, that code-like reductions cannot prove the hardness of approximating Clique within a factor \sqrt{n}, of approximating Vertex Cover within a factor 1.5, and of coloring a 3-colorable graph with O(\log n) colors.

The above results help explain why proving really good inapproxima -bility results has been difficult.

In fact, we will argue that it is inherently difficult to come up with reductions that are not code-like. We provide some evidence supporting this view-point.

(The talk will be self-contained.)

Schedule for the Spring Semester

Jan. 25: Sridhar Rajagopalan: On the value of Planning and Capital
Feb. 1: Neal Young: Randomized Rounding Without Solving the Linear Program
Feb. 8: Richard Lipton: Speeding Up Computations via Molecular Biology
Feb. 15: no meeting; but note the DIMACS Complexity day, Feb. 17
Feb. 22: Shiyu Zhou: Explicit Dispersers with Polylog Degree
Mar. 1: Bhaskar DasGupta: Analog versus Discrete Neural Networks
Mar. 8: no meeting
Mar. 22: Eric Allender: Sparse Hard Sets for P Give Space-Efficient Algorithms
Mar. 29: Robert Beals: Symmetric Logspace is Closed Under Complement
Apr. 5: no meeting; but note Columbia University's Theory Day, April 7
Apr. 12: Kathleen Romanik: A 3-Dimensional Visibility Representation for Graphs
Apr. 19: Bernard Chazelle: Spectral Techniques for Proving Lower Bounds
Apr. 26: Sanjeev Arora: Reductions, Codes, PCPs, and Inapproximability
May 10: Rajeev Alur: Automatic Verification of Timed and Hybrid Systems
May 17: Mikkel Thorup: An O(log log n) Priority Queue

Document last modified on April 18, 1995