## Advanced Complexity II - 0366.41??.??

### Instructor: Muli Safra

The course would cover topics further advanced than Advanced Complexity, in particular the proof of the PCP characterization of NP and inapproximabilty for some approximation problems.

Lectures:

PCP

Codes

Consistency Tests (locally testable)

Low Degree Test: Proof

PCP proof: 1 2 3

Inapproximability

Fourier Definitions, Junta Test, Friedgut Theorem

Hardness of Vertex-Cover

Extractors from Polynomials

Lattices

#### Assignments:

 Assignment #1: We saw that dimension-d degree-r polynomials are alpha-codes; for which alpha? Write down the expression for the dimension-d low-degree-extension (LDE) of a string sigma in {0,1}n Show that for a boolean function f there exsits a subset I of [n] of size n/10 so that f is 1/log n far from a Junta over I Finite-Field Geometry, in 3-dimensional space: Show that  a. Two planes cannot intersect by only a point; They are either parallel or intersect by a line. b. For any given line l, only a |F|-1 fraction of the planes do not intersect l. Show that, for a given assignments A, and let G(A) be the consistency graph for A:         g(G[A]) £  g(A) + |Á|-1 Show that the algorithm, described in class, for clique'ing the graph: a. Removes at most 3*(sqrt(beta(G)))* (1/2)|G|^2 of G's edges. b. The resulting graph is indeed transitive. Prove the theorem [RaSa] for general d, and for delta >= |F|^c (or at least for delta >= d*(|f|^c)) Prove the "Lemma of Large Clique": In a transitive graph G, whose edges are a fraction g of the pairs of vertices, there must be at least one clique of at least g(G)*|G| vertices. Prove the Large Clique’s Consistency Lemma over G(A):     A large (> |Á|-½) clique in G(A) agrees almost everywhere with a single degree-r polynomial Assignment #3: Given an assignment to a longcode A:BP[R] ® {0, 1}, show that for any (constant) d > 0, there is a constant h(d), which depends on d however does not depend on R, such that:       | {e Î R | D(Ee, A) > ½ + d } | £ h(d) where D(A1, A2) is the fraction of bits A1 and A2 differ on

 Assignment #5: Assuming the Plane-vs-Plane test true, show the Point-on-Plane test true. Show a Karp-reduction from SVP to CVP (preferably deterministic, otherwise probabilistic)