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
- Computational Complexity Theory (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- P versus NP problem - Wikipediaen.wikipedia.org
- ProofsArgsAndZK.pdfpeople.cs.georgetown.edu
- 15-855: Graduate Computational Complexity Theory, Fall 2017cs.cmu.edu
- 1404.5236 Sum-of-Squares Proofs and the Quest toward Optimal Algorithmsarxiv.org
- Shtetl-Optimized >> Blog Archive >> Ten Signs a Claimed Mathematical Breakthrough is Wrongscottaaronson.blog
- Computational Complexityblog.computationalcomplexity.org
- pnp.pdfscottaaronson.com
- What's new | Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Taoterrytao.wordpress.com
- Logic in Computer Sciencecourses.grainger.illinois.edu
- Complexity class - Wikipediaen.wikipedia.org
- Proofs, beliefs and algorithms through the lens of Sum of Squaressumofsquares.org