CSC 2429: Propositional Proof Complexity
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
Course Information Sheet
CLASS SCHEDULE AND NOTES
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
OLD SCRIBE NOTES (From earlier course many years ago..MAY CONTAIN ERRORS)
OTHER REFERENCES
Razborov's Proof Complexity Course
Notes from Razborov's Course