演讲人： Andrej Bogdanov The Chinese University of Hong Kong
时间： 2009-04-24 10:00-2009-04-24 11:30
地点：FIT Building 1-222, Tsinghua University
内容：

DESCRIPTION:
A key step in the proof of PCP theorems is soundness amplification. Roughly, this is a collection of methods that improves the soundness of PCPs at the cost of the alphabet size, while preserving the query complexity. Until recently the only soundness amplification method was the parallel repetition theorem of Raz, but in the last two years several new approaches have been proposed.
Recent interest in parallel repetition has been partially motivated by Khot's unique games conjecture. Some researchers believed that parallel repetition could be used to prove the conjecture, until these hopes were dashed last year by Raz himself. It is possible that recent work on soundness amplification may also be related to the unique games conjecture. As of now no progress has been made in this direction.
The objective of the seminar will be to understand some of these approaches to soundness amplification and their relation to the unique games conjecture.

In particular I propose to focus on the following four methods:
(5)    Dinur's gap amplification theorem.
This is the key step in Dinur's proof of the PCP theorem. It seems that Dinur's proof only applies to the regime where the soudness is large. One possible direction of investigation if some variant of this construction might also work when the soundness is small.
(6)    Raz's parallel repetition theorem.
This is the "standard" way of amplifying hardness and a key step used in most tight NP-hardness of approximation results. Raz's proof was viewed as very difficult, but it was recently simplified by Holenstein and some parameters were improved by Rao.
(7)    The IKW direct product PCP.
This is a very recent approach of Impagliazzo, Kabanets, and Wigderson that seems to achieve a similar effect to parallel repetition using "direct-product"-like theorems from average-case hardness amplification.
(8)    The Moshkovitz-Raz PCP.
Also a very recent algebraic PCP construction of Moshkovitz and Raz seems to achieve similar (even better in some respect) parameters as parallel repetition.

LOGISTITCS: The plan is to meet twice a week in the course of a month (late April and May) and discuss some of these papers. I plan to give a motivating introduction and "jump-start" the discussion by presenting one of the topics, but after that I expect others to lead the discussion on the other papers.

WHAT'S IN IT FOR ME?
These are difficult papers that will take time to read.
If you are interested I suggest you choose one of the papers early on and try to master it well enough so you feel comfortable presenting it in the seminar.
I don't expect us to be able to cover everything.
Each of these papers may take 2-3 meetings to discuss.
Why should you be interested? PCPs are perhaps the most fruitful research topic in complexity theory. Many known theorists made their name by proving PCP theorems as graduate students!
It is a proven recipe for becoming famous. Besides, it is lots of fun.
 

个人简介: