# 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

Document last modified on April 18, 1995