COMP 598 Fall 2020 - Proof Complexity
The study of this question belongs to the field of propositional proof complexity. Since proofs appear everywhere in computer science, proof complexity has many deep connections with some of our central open problems:
COMP 598 Fall 2020 - Proof Complexity COMP 598 Proof Complexity: Algorithms and Lower Bounds Instructor Name: Robert Robere Email: robere AT cs DOT mcgill DOT ca Course Information Sheet Information Sheet --> Lectures When: Tuesday, Thursday from 2:35-3:55 Where: Online [outline] Lecture Notes [Lecture 1] - Introduction [Lecture 2] - Propositional Proof Systems, Resolution (Definition, Completeness) [Lecture 3/4] - Resolution (Tree-Like, Complexity Measures, PHP Lower Bounds, Width-Size Relation) [Lecture 5] - Resolution (Width-Size Relation cont., Tseitin Formulas, Expander Graphs, Random k-C
saved by
related reading
- 15-855: Graduate Computational Complexity Theory, Fall 2017cs.cmu.edu
- Logic in Computer Sciencecourses.grainger.illinois.edu
- dec9.pdfpeople.seas.harvard.edu
- Fall 2026boazbk.github.io
- CS 70 Fall 2026eecs70.org
- Tim Roughgarden's Lecture Notestimroughgarden.org
- Introduction to Program Synthesispeople.csail.mit.edu
- ProofsArgsAndZK.pdfpeople.cs.georgetown.edu
- 15-859T: A Theorist's Toolkit 2013cs.cmu.edu
- Total Search @ STOC 2025sites.google.com
- Computational Complexity Theory (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- Mathematics for Computer Sciencepeople.csail.mit.edu