ColloquiaTalk: Subash Khot on Monday, February 17, 2003

[Margery Ishmael]

----------------------------------------------------------------------------

DEPARTMENT OF COMPUTER SCIENCE - TALK

Monday, February 17, 2003 at 2:30 pm, Ryerson 251

----------------------------------------------------------------------------

Speaker: SUBASH A. KHOT, Princeton University

Title: "Probabilistically Checkable Proofs (PCPs) and
Hardness of Approximation"

Abstract:
Many optimization problems of theoretical and practical
interest are NP-complete, meaning it is impossible to compute
exact solutions to these problems in polynomial time unless
P = NP. A natural way to cope with this curse of NP-completeness
is to seek approximate solutions instead of exact solutions. An
algorithm with approximation ratio C computes, for every problem
instance, a solution whose cost is within a factor C of the
optimum. Optimization problems exhibit a wide range of behavior
in their approximability. It is well-known that Bin-Packing has
an approximation algorithm with ratio 1+epsilon for every positive
epsilon. In theory jargon, we say that Bin-Packing has a
polynomial-time approximation scheme (PTAS). However, it wasn't
known till the early 90s whether problems like MAX-3SAT, Vertex
Cover, and MAX-CUT have a PTAS. A celebrated result called the
PCP Theorem finally showed that these problems have no PTAS
unless P = NP. Such results that rule out the possibility of good
approximation algorithms (under complexity theoretic assumptions
like P != NP) are called inapproximability results or hardness of
approximation results.

The PCP Theorem has an equivalent formulation from the point of
view of proof checking. The PCP theorem states that every NP-
statement has a probabilistically checkable proof, i.e. a proof
which can be "spot-checked" by reading only a constant number of
bits from the proof. These bits are selected by a randomized
process using a very limited amount of randomness. The checking
process always accepts a correct proof of a correct statement
and rejects any cheating proof of an incorrect statement with
high probability. The term "holographic proof" is sometimes used
to highlight this feature that a cheating proof must be wrong al-
most everywhere and therefore, can be detected by a spot-check.
The discovery of the connection between proof checking and
inapproximability results is one of the most exciting theoretical
developments in the last decade. Since then, PCPs have led to
several breakthrough results in inapproximability theory, e.g.
tight hardness results for Clique, MAX-3SAT, and Set Cover. My
work continues this line of research and I obtain (sometimes with
coauthors) new hardness results for (1) Graph and Hypergraph
Coloring (2) Vertex Cover in Hypergraphs (3) Constraint Satisfac-
tion Problems (4) Clique-size and Chromatic Number of Graphs.
In this talk, I will give a survey of PCPs, known hardness
results obtained via PCP constructions, and techniques involved
in building PCPs.

* Refreshments will follow in Ryerson 255*

Hosts: Laszlo Babai & Eric Vigoda




=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margery Ishmael
Secretary to the Chairman, Department of Computer Science
The University of Chicago
1100 E. 58th Street, Chicago, IL. 60637-1581
tel. 773.834.8977 fax. 773.702.8487
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-