Explore the evolution and significance of Satisfiability (SAT) in computer science through this one-hour lecture by Avi Wigderson from the Institute for Advanced Study. Delve into the 50-year history of SAT and its central role in the Theory of Computing. Examine recent breakthroughs, algorithmic approaches to lower bounds, and the PID problem. Investigate proof identities, inequalities, and the state of current knowledge in the field. Gain insights into the theory of computation and its position at the core of computer science research.
Overview
Syllabus
Introduction
Context
Questions
Is it possible
A recent breakthrough
Low bounds through algorithms
The pid problem
Proof identities and inequalities
Problems
Algorithms
Conclusion
QA
State of ignorance
Question time
Theory in the center
Theory of computation
Summary
Taught by
Simons Institute
Related Courses
-
Computer Science: Algorithms, Theory, and Machines
-
Circuit Lower Bounds from Algorithm Design - An Overview I
-
Graph Theory and Algorithms
-
Hardness Magnification for All Sparse NP Languages
-
Great Ideas in Theoretical Computer Science - Approximation Algorithms
-
Is it Easier to Prove Statements that are Guaranteed to be True?
