Advanced Topics 3 (236603):
Lower Bounds for Boolean and
Material covered so far:
- 20.3: Proved Shannon's Theorem. Started proving Lupanov's theorem.
- 27.3: Finished the proof
of Lupanov's theorem. Proved a 3(n-1) lower
parity. Defined formulas and showed the tight relation between depth to size.
- 3.4: Proved formula lower
bounds by Neciporuk, Khrapchenko.
- 10.4: Subbosatovskaya's
method. Andreev's lower bound.
- 24.4: Karchmer-Wigderson
theorem about communication complexity and formula depth.
- 1.5: K-W lower bound for
monotone depth of ST-Connectivity.
- 8.5: Razborov's
approximation method. Lower bound for monotone circuits computing
- 15.5: Lower bound for
monotone circuits computing Clique(n,k).
- 22.5 Hastad switching
lemma and lower bounds for AC^0 circuits.
- 5.6 Introduction to
arithmetic circuits and survey of known bounds.
- 12.6 P=NC^2
for arithmetic circuits.
- 19.6 Lower bounds of
Strassen and Baur-Strassen.
- 26.6 The partial
derivatives methods. Lower bounds for depth 3 circuits and for
- 3.7 Valiant's argument
for linear size logarithmic depth graphs. More approaches to proving lower
- Exercise 1 pdf, ps. Hand in date: April 23rd.
- Exercise 2
ps. Hand in date:
- Exercise 3
Hand in date: July 6th.
Hand in date: July 20th.