Google Scholar

Monday, September 19, 2005

TUTORIAL

I am giving talks on Thursday 22, 4pm, Tuesday 27, Thursday 29, Physics Department, the University of Queensland

Part A
a A proof of NP = PCP(log n, 1)
A proof that NP is equal to a set of languages accepted by probalistic turing machines with log n random bits and the constant number of queries to an oracle which has access to a proof. A proof is based on arithmetization and low-degree techniques.
b Low Degree Techniques
a1 LKFN tests (Lund, Fortnow, Karloff, Nisan)
LKFN test method are necesary to prove PCP theorem. It played a role to prove other fundamental results: IP = PSPACE, and MIP = NEXPTIME.
Assume that f: F^m -> G be a polynomial of degree at most d in every variable, with F beeing a finite field and G a field extension of F. Suppose H \subseteq F, H is an arbitrary subset of F
Using LKFN method we can check if \sum_{u \in H^m} f(u) = 0 efficiently (with some limitations on the number of random bits and the number of bits read from a "proof") such that
if sum = 0 then there exist a proof such that LKFN test output accepts with probability 1
if sum \not = 0, then LKFN test reject with probability at least 3/4 for all proofs
a2 Low degree tests
Tests developed by Arora, Lund, Motwani, sudan, Szegedy for checking if given function is \delta-close to a polynomial of degree at most d. (Proof by Hougardy, Promel, Steger)
3 Applications of PCP theorem
Non-approxmability of MAX-SNP hard problems, coloring and clique problems
Appendix Optimized version of PCP theorem


Part B. Quantum PCP theorem (result of Ran Raz presented at FOCS 2005)