Winter, 2017

** Students should consult this page at least once a week
for important information. **

ANNOUNCEMENT Feb 18. The homework is ready! See below. Also below please look at topics for course presentation. Your topic choice is due by March 6!! Class this coming week (Feb 22) is cancelled because of the winter break. Next class is Mar 1 and I plan to attend class in person!

** Lectures: ** Wednesday 3-5 Pratt 266

** Instructor: ** Toniann Pitassi, email: toni@cs

Office: Sandford Fleming 2305A, 978-3695

Office Hours: by appointment

**
CLASS SCHEDULE AND NOTES
**

- Lecture 1 slide: Survey on Proof Complexity
- Lectures 1-2 Notes (Resolution Upper Bounds and Lower bounds for PHP)
- Lecture 3 by Mike Molloy (no notes): Size/Width Tradeoff, random CNF, and ABM paper (see below for links)
- Lecture 4 Notes (Crash Course in Bounded Arithmetic)
- Lecture 5 by Alasdair Urquhart (no notes): Lower bounds for AC0-Frege proofs of PHP (see below for links)
- Lecture 6 Notes (Cutting Planes and Interpolation)
- Lecture 7 Notes (Algebraic Proof Systems)
- Lecture 8: applications of proof complexity to algorithmic analysis. See Slides from Lecture 1.

** HOMEWORK AND PRESENTATIONS **

** PAPERS (I will be adding to this as the course continues)**

- Beame-Karp-Pitassi-Saks paper on resolution (Lecture 1)
- Simplified and Improved Resolution Lower bounds (Lecture 1)
- Resolution and the Weak Pigeonhole Principle (Lecture 2)
- Maciel, Pitassi and Woods paper on the WPHP (Lecture 2)
- Ben-Sasson and Wigderson paper on size-width tradeoffs (Lecture 3)
- Achlioptas, Beame, Molloy (Lecture 3)
- Buss, Bounded Arithmetic, (Lecture 4)
- Fu and Urquhart's paper (Lecture 5)
- Pudlak, paper on Cutting Planes lower bounds (Lecture 6)
- Bonet, Pitassi, Raz paper on Interpolation and Automatization (Lecture 6)
- Pitassi, Tzameret, Survey paper on Algebraic Proof Complexity (Lecture 7)
- Aleknovich, Buss, Moran, Pitassi paper on minimum proof length problem
- Aleknovich, Razborov paper on nonautomatizability of Resolution
- Dissertation by Beyersdorff, Disjoint NP Pairs and Propositional Proof Systems

** SURVEY PAPERS **

- Survey Article by Razborov
- Survey article with Iddo Tzameret on Algebraic Proofs
- Notes from Beame's IAS Lectures
- Beame and Pitassi survey article
- Nathan Segerlind's survey article (more recent and comprehensive)
- Notes from Buss's McGill Lectures
- Buss's paper on proof theory

** OLD SCRIBE NOTES (From earlier course many years ago..MAY CONTAIN ERRORS) **

- Lecture 1
- Lecture 2
- Lecture 3
- Lecture 4
- Lecture 5
- Lecture 6
- Lecture 7
- Lecture 8
- Lecture 9
- Lecture 10
- Lecture 11
- Lecture 12

** OTHER REFERENCES
**