Computer Science

0368.4159

Spring 2011

Open
to: undergraduates and graduate students who have taken the complexity
class. Students who have not taken complexity yet need a special approval
from the lecturer.
Grading: either:
·
By exam (mandatory for undergraduate
students), or,
·
(a more difficult)
takehome exam.
· Exercises are optional. A random sample will
be checked and the grade will not be recorded. Exercises are meant to give
students a chance to practice and make sure they understand the lectures.
You are very welcome to:
· Choose the problems you
would like to solve,
· Work with others on a
problem,
· Discuss it with me, and
· Ask me to check your
solution.
Problem file 
Last updated: after lecture 10.
Date 
Topic 
1. 21/12/11 The Kakeya set problem. 
Basic lower bound: Z. Dvir. On the size of Kakeya sets in finite fields. J. Amer. Math. Soc., 22:10931097, 2009. [ bib  .pdf ] Upper bound: S. Saraf, M. Sudan. Improved lower bound on the size of Kakeya sets over finite fields. http://arxiv.org/abs/0808.2499 
2. 07/03/11 Multiplicities of multivariate polynomials over finite fields. Mergers 
Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan. Extensions to the method of multiplicities, with applications to kakeya sets and mergers. In FOCS '09: FOCS, pages 181190, 2009. [ bib  .pdf ] 
3. 14/03/11 L,RL,NL,
BPL, STCON and USTCON. Random walks on undirected graphs
via algebraic expansion. USTCON in RL. 
Space complexity: Arora – Barak – Chapter 4. Expanders: Luca Trevisan, Computational complexity  2008 Lectures: 8 –
RL and random walks
Lecture 9 – Cheeger inequality (we skipped the proofs),
Lecture 10 – Cheeger is tight (we skipped completely),
Lecture 11 –
convergence to uniform and mixing lemma

4. 28/03/11 
The privacy
amplification problem. Extractors. Pairwise
independence, 2universal hash functions. ILL,
optimal entropy loss extractors [NZ:
Randomness is Linear in Space]. Derandomization
vs. Pseudorandomness. Cheating
uniform classes vs. cheating nonuniform classes. 
5. 04/04/11 
PRG against BPL (and polynomial width branching
programs). 1.
Extending m to 2m. A.
Using privacy amplification B.
Using expander mixing lemma C.
“Strong” “expander mixing lemma” using 2universal hash
functions. 2.
Extending approach A to many blocs [INW: Pseudorandomness
for Network Algorithms ] 3.
Extending approach C to many blocks [N: RL is contained in SC] 
6. 11/04/11 
Cayley graphs. Character of Abelian groups. The spectrum of the hypercube. The
replacement product. 
7. 2/05/11 
An explicit constructions of a constant degree graph with constant spectral gap.[AB,16.4], Omer Reingold, Salil. Vadhan, Avi. Wigderson. 
8. 16/05/11 
Omer Reingold, Undirected STConnectivity in LogSpace [AB, 16.5], Finding a path between s and t. Universal traversal sequences. Short UTS exist. Explicit UTS for πlabelled graphs. 
9. 23/05/2011 
E. Rozenman,
S. Vadhan 
10. 30/05/2011 
Luca Trevisan.
Extractors and Pseudorandom Generators J. of the ACM, 48(4):860879, 2001. 
11. 6/6/2011 
V. Kabanets
and R. Impagliazzo, Derandomizing Polynomial Identity Tests Means Proving
Circuit Lower Bounds . 
12. 13/6/2011 
List decoding RS codes. Sudan’s
Lecture 12
(10/29): Local unique decoding RM codes. 
13. 22/6/2011 
Local list decoding RM codes. 
Date 
Topic 
More details 
24.1.08 Tail inequalities 

A comparison for X=sum(X_i) with: 1. no constraints, 2. pairwise independence and 3. full independence 
24.1.08 Pairwise independence. 


31.1,7.2,14.2
Complexity background 
31.1.08 basic notions 

More connections between the uniformityand nonuniform worlds. 

DLOG 

USTCON. SL. A probabilistic logspace algorithm solving USTCON using random walks. 

An explicit constructions of a constant degree graph with constant spectral gap. [AB, 16.4], 

A deterministic logspace algorithm for undirected connectivity. 
Omer Reingold, Undirected STConnectivity in LogSpace [AB, 16.5], Finding a path between s and t.
