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
Explore this link on the map →saved by
related reading
- 15-855: Graduate Computational Complexity Theory, Fall 2017cs.cmu.edu
- Computational Complexity Theory (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- ProofsArgsAndZK.pdfpeople.cs.georgetown.edu
- P versus NP problem - Wikipediaen.wikipedia.org
- Computational Complexityblog.computationalcomplexity.org
- 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
- Shtetl-Optimized >> Blog Archive >> Ten Signs a Claimed Mathematical Breakthrough is Wrongscottaaronson.blog
- 1404.5236 Sum-of-Squares Proofs and the Quest toward Optimal Algorithmsarxiv.org
- P vs NP and its application to zero knowledge proofs | RareSkillsrareskills.io
- Complexity Theory’s 50-Year Journey to the Limits of Knowledge | Quanta Magazinequantamagazine.org