0368410501 
[Wdnesday
[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; ErrorCorrectingCodes;
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.

Randomness in computation (BPP and RL) 

Probabilistic Checking of Proofs (PCP) and Hardness of Approximation; UGhardness 

ErrorCorrectingCodes; LocalTesting 

Derandomization, Pseudo random generators 

Interactive Proofs; ZeroKnowledge Proofs 

Advanced Hardness of Approximation 

Harmonic Analysis of Boolean functions 

Embedding 

Lattice problems 






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.





















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
Noizeinsensitive Boolean functions are juntas
1. The Circuit Evaluation problem is as follows: Given a circuit C and input x, does C accept x? Prove this problem is Pcomplete.
2. Given a probabilistic
Polytime 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 ISCLIQUE(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 ISCLIQUE[c/sqrt(n),c/sqrt(n)] is NPhard.
Due Date: Dec 3, 08