# Advanced Computational Complexity Theory

 0368-4105-01

[Wdnesday 1-4pm, Schreiber 006]

 [Syllabus]

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 ) Hardness vs Randomness: part 1  & part 2(PPT) PRG for SPACE Bounded Computations: part 1 & part 2 (PPT ) Circuit Depth and Space Bounds: PPT 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