DIMACS Seminar on Theoretical Computer Science

Title:

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

Speaker:

Sanjeev Arora

Princeton University

Place:

DIMACS Seminar Room, CoRE Building, Room 431

Busch Campus, Rutgers University

Time:

10:00 AM

Wednesday, April 26, 1995

Abstract:

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 3: YOUR NAME HERE
May 10: Rajeev Alur: Automatic Verification of Timed and Hybrid Systems
May 17: Mikkel Thorup: An O(log log n) Priority Queue