Advanced Computational Complexity Theory

0368-4105-01

[Wdnesday 1-4pm, Schreiber 006]

 

Prerequisite Course: Complexity Theory (undergraduate)

Instructor: Muli Safra


The course covers fundamental concepts of Computational Complexity Theory and Theory of Computer Science. We will start with basic techniques; discuss Hardness of Approximation; Error-Correcting-Codes; Local Tests; Randomness in Computations; Derandomization and a little Cryptography. When necessary we incorporate Analysis of Boolean functions. If time permit we'll go over advanced subjects of research and techniques.

Topics:

Randomness in computation (BPP and RL)

Probabilistic Checking of Proofs (PCP) and Hardness of Approximation; UG-hardness

Error-Correcting-Codes; Local-Testing

De-randomization, Pseudo random generators

Interactive Proofs; Zero-Knowledge Proofs

Advanced Hardness of Approximation

Harmonic Analysis of Boolean functions

Embedding

Lattice problems

Primes in P

 

 

 

Lecture Notes

Fos introduction to some of the subjects see www.tau.ac.il/~safra/ -- follow the link to the undergraduate complexity course.

Some parts of the course we will be using presentations based on lecture notes subscribed by students in a course given by Oded Goldreich at the Weizmann Institute in 1999.

P vs NP: part 1 & part 2 (PPT )

 

Space Complexity: part 1 & part 2 (PPT )

 

Probabilistic Computations: part 1 & part 2 (PPT )

 

P/poly and PH: part 1 & part 2 (PPT )

 

#P; Pseudo Random Generators: part 1 & part 2 (PPT 1 & 2)

 

 

Zero Knowledge Proofs: part 1 & part 2  (PPT1 PPT2 )

 

 

Hardness vs Randomness: part 1  & part 2(PPT)

 

PRG for SPACE Bounded Computations: part 1 & part 2 (PPT )

 

Circuit Depth and Space Bounds: PPT

 

 

PCP: PPT PCP, Introduction, Encodings, Consistency Tests

 

 

 

 

 

 

Some of the course involves Analysis of Boolean Functions, Coding Theory, Testing. Presentation on these subjects can be found at:

Analysis and Code Testing Intro Codes and Tests.

Hardness of Approximating linear equations, Vertex-Cover

Noize-insensitive Boolean functions are juntas

 

Assignments

Assignment #1:

1. The Circuit Evaluation problem is as follows: Given a circuit C and input x, does C accept x? Prove this problem is P-complete.

2. Given a probabilistic Poly-time algorithm that accepts input in language L with probability >p1 and accepts input outside L with probability <p2<p1 (assume these are two distinct constants). Describe how to utilize this algorith to design an algorithm that errs on L with probability e(-k) for any k (where the time complexity is linear in K). Prove that claim.
In addition, prove the claim used in the BPP in Sigma2, namely, that this algorithm, with the right parameters, errs with probability 1/3m, where m is the number of random bits it uses.

3. Pprove the following (multiplicative) Chernoff bound:

If X~B(n,p) then
Pr[X>(1+d)E[X]] < e^(-E[X]*d^2/4) 

4. Define the language IS-CLIQUE(a,b) to be all graphs to be all graphs that have an 
IS of fractional size a AND a CLIQUE of fractioal size b. 
Show that for some c IS-CLIQUE[c/sqrt(n),c/sqrt(n)] is NP-hard.

5*. Find a problem complete for EXPTIME, and show it is indeed complete.

Due Date: Dec 3, 08