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.

 

Lectures:

PCP

Introduction

Error Correcting

Codes

Quadratic Solvability

Consistency Tests (locally testable)

Low Degree Test: Proof

Consistent Readers (locally decodable)

PCP proof: 1 2 3

Inapproximability


Tight Hardness Results

Others

Fourier Definitions, Junta Test, Friedgut Theorem

Hardness of Vertex-Cover

Extractors from Polynomials

Noize-insensitive boolean functions are juntas

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

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