Computer
Science

0368.4159

Fall 2008 
Thursday, 20/3, 101 (Kaplun 118)
Thursday, 27/3, 101 (Kaplun 118)
Friday, 28/3, 101 (Kaplun 118)
Thursday, 3/4, 101 (To be announced later)
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:
· There will be a quiz after 4 classes (Must pass. 20% of final grade).
· In addition each student will have to present a paper (70% of final grade).
· 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 14.3.08
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 

7.2.08 BPP seems like not being strong enough for NP 


14.2.08 More connections between the uniformityand nonuniform worlds. 


Derandomization vs. circuit lower bounds.

14.2.08 Does a derandomization exist for ACIT? 21.2.08 No derandomization before we prove circuit lower bounds 



28.2.08, 6.3.08 Circuit lower bounds suffice for derandomization. 
So may be Identity testing is not in P?


13.3.08 How about circuit lower bounds? 





undirected connectivity in RL

13..308
20.3.08 
USTCON. SL. A probabilistic logspace algorithm solving USTCON using random walks. λ_{2} and λ=max{λ_{2,}λn}. Small λ implies rapid mixing. (HLW, sec 3). The mixing lemma. (HLW, sec 2.4). Small λ implies small diameter. Small λ implies implies edge expansion. (LHS of HLW Thm 4.11, sec 4.5.1).

Expanders 
27.3.08 The zigzag construction

An explicit constructions of a constant degree graph with constant spectral gap. [AB, 16.4], Omer
Reingold, Salil.
Vadhan, Avi.
Wigderson. 
A deterministic logspace algorithm for undirected connectivity.

28.3.08 2.4.08 
Omer Reingold, Undirected STConnectivity in LogSpace [AB, 16.5], Finding a path between s and t.

================================================================================
M. Luby, A simple parallel algorithm for the maximal independent set problem
V. Kabanets, R. Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds. Section 7 (we did the other direction in class).
a. V. Arvind, J. Kobler, U. Schoning, R. Schuler. If NP has polynomial size circuits then MA=AM.
b. N. Vinodchandran, A note on the circuit complexity of PP.
J. Y. Cai. S_{2}^{p} ⊆ BPP^{NP}.
V. Kabanets, J. Y. Cai. Circuit minimization problem.
R. Santhanam, Circuit Lower Bounds for MerlinArthur Classes: STOC 2007.
Z. Dvir. On the size of Kakeya sets in finite fields. J. of the AMS (to appear)., 2008. [ bib  .pdf ]
S.
Aaronson, A. Wigderson, Algebrization: A new barrier in complexity
theory. STOC
08
[
Draft of full version (pdf) ] [
Draft of full version (ps) ]
N. Alon and B. Sudakov, Bipartite subgraphs and the smallest eigenvalue (Edge expansion implies small λ_{2} (RHS of HLW, Thm 4.11, sec 4.5.2)).
The AlonBoppana lower bound on the second largest eigenvalue. Sec 5.2 of Shlomo Hoory and Nathan Linial and Avi Wigderson, Expander Graphs and their applications
J. Friedman, On the Second Eigenvalue and Random Walks in Random dRegular Graphs .
E. Rozenman and S. Vadhan Derandomized squaring of graphs.
O. Reingold, L. Trevisan and S. Vadhan, Pseudorandom walks on regular digraphs and the RL vs. L problem. STOC 2006.
K.M. Chung, O. Reingold and S. Vadhan, ST Connectivity on Digraphs with Known Stationary Distribution, CCC 2007.
R. Impagliazzo, N. Nisan, and A. Wigderson. Pseudorandomness for Network Algorithms
M. Saks and S. Zhou BP_{H}SPACE⊆DPSACE(S^{3/2})
D. Zuckerman, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number (Theory of Computing, 2007)
V. Guruswami, C. Umans, and S. Vadhan. Unbalanced Expanders and Randomness Extractors from ParvareshVardy Codes.
S. Miller, R. Venkatesan. Spectral Analysis of Pollard Rho Collisions
Chvatal's lecture notes on the AKS sorting network.