Advanced Complexity II - 0366.41??.??

Prerequisites: Advanced Complexity

Spring Semester 2003: Wednesday 4-7

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.





Error Correcting


Quadratic Solvability

Consistency Tests (locally testable)

Low Degree Test: Proof

Consistent Readers (locally decodable)

PCP proof: 1 2 3


Tight Hardness Results


Fourier Definitions, Junta Test, Friedgut Theorem

Hardness of Vertex-Cover

Extractors from Polynomials

Noize-insensitive boolean functions are juntas




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
  1. 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
  2. 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.
  3. Show that, for a given assignments A, and let G(A) be the consistency graph for A:
            g(G[A])   g(A) + ||-1
  4. 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.
  5. Prove the theorem [RaSa] for general d, and for delta >= |F|^c
    (or at least for delta >= d*(|f|^c))
  6. 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.
  7. Prove the Large Cliques Consistency Lemma over G(A):
    A large (> ||-) clique in G(A) agrees almost everywhere with a single degree-r polynomial
Assignment #3:
    1. 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)

      D(A1, A2) is the fraction of bits A1 and A2 differ on

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