CS 860: Advanced Topics in Algorithms and Complexity
Fall 2008: Randomness and Complexity
Schedule of Lectures
The future remains uncertain; history may contain mistakes. Caveat lector.
- Sept. 9–18:
- Background in computational complexity
- Machines and time bounds
- Circuits as a computational model
- Uniform circuits: size ≈ time
- Non-uniform circuits: the class P/poly
- Randomized computations
- The classes RP and BPP
- BPP ∈ P/poly
Space-bounded computations
- The classes RL and NL
- Reachability in directed and undirected graphs
- Sept. 23
-
Daniel Ivan presented Sipser's paper,
a non-trivial use of expander graphs in
computational complexity.
- Sept. 25
- Background in algebra and combinatorics
- Eigenvalues and convergence of random walks
- Expander graphs
- Finite fields (very quickly)
- Sept. 30, Oct. 1
-
Sergei Savinov presented Impagliazzo
and Zuckerman's paper
discussing the number of random bits needed to get good error
rates.
- Oct. 7, 9
-
Jalaj Upadhyay will present
Nisan and
Wigderson's pseudo-random generators.
- Oct. 14, 16
- Jakub Truszkowski will present
a nice
recursive construction of good expander graphs.
- Oct. 21, 23
- Gus Gutowski will present
Reingold's algorithm to
test connectivity of undirected graphs in log space.
- Oct. 28, 30
- Someone may present
Dinur's simplification
of the original (horrendously long) proof that some NP
problems are NP-hard to approximate.
Or we may decide that the simplification is still too hard
to present in one week. Check this space for updates.
Parts of this file translated from
TEX
by
TTH,
version 3.40.
On 10 Sep 2008, 14:34.