### 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)

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)