We show that the NP-Complete language 3Sat has a PCP verifier that makes two queries to a proof of almost-linear size and achieves sub-constant probability of error. The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the second query.

Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small) constant error and polynomial size. There were also PCP Theorems with sub-constant error and almost-linear size, but a constant number of queries that is larger than 2.

As a corollary, we obtain a host of new results. In particular, our theorem improves many of the hardness of approximation results that are proved using the parallel repetition theorem. A partial list includes the following:

1) 3Sat cannot be efficiently approximated to within a factor of 7/8+o(1), unless P=NP. This holds even under almost-linear reductions.
Previously, the best known NP-hardness factor was 7/8+\epsilon for any constant \epsilon>0, under polynomial reductions (Hastad 1997).

2) 3Lin cannot be efficiently approximated to within a factor of 1/2+o(1), unless P=NP. This holds even under almost-linear reductions.
Previously, the best known NP-hardness factor was 1/2+\epsilon for any constant \epsilon>0, under polynomial reductions (Hastad 1997).

3) A PCP Theorem with amortized query complexity 1 + o(1) and amortized free bit complexity o(1). Previously, the best known amortized query complexity and free bit complexity were 1+\epsilon and \epsilon, respectively, for any constant \epsilon > 0 (Samorodnitsky and Trevisan 2000).

I will aim the talk to a non-PCP audience and in 1 hour will mainly give an introduction and won't go too much into proofs (if people are interested, I will be able to give a short description of the main ideas of the proof on a different occasion).

Joint work with Dana Moshkovitz