Advanced Topics 3 (236603):

Lower Bounds for Boolean and Arithmetic Circuits

Info:

• Lecture: Monday 10:30-12:30.
• Room: Taub 5.
• Lecturer: Amir Shpilka
• Syllabus

Books and references:

• The Complexity of Boolean Functions by I. Wegener.
• Lecture Notes on Circuit Complexity by U. Zwick.
• Lecture Notes on Arithmetic Circuits by R. Raz.
• Algebraic complexity theory by P. Burgisser, M. Clausen and M. A. Shokrollahi.

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 bound for
  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.
• 17.4: Passover.
• 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 Clique(n,3).
• 15.5: Lower bound for monotone circuits computing Clique(n,k).
• 22.5 Hastad switching lemma and lower bounds for AC^0 circuits.
• 29.5. No class.
• 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 non-commutative formulas.
• 3.7 Valiant's argument for linear size logarithmic depth graphs. More approaches to proving lower bounds.

Exercise:

• Exercise 1 pdf, ps. Hand in date: April 23^rd.
• Exercise 2 pdf, ps. Hand in date: June 5^th.
• Exercise 3 pdf, ps. Hand in date: July 6^th. 
• Exercise 4 pdf, ps. Hand in date: July 20^th.