Explore the intricacies of complexity theory in this 42-minute ACM conference talk. Delve into key concepts such as the Multiplicity Theorem, Programsized Complexity, and Binary Counter. Examine abstract tests and consider whether improvements can be made. Investigate the connections between statistical physics and algorithmic questions, and analyze the Pots Model in relation to computational problems. Gain insights into tree evaluation techniques and draw meaningful conclusions about the field of complexity.
Overview
Syllabus
Introduction
Multiplicity Theorem
Programsized Complexity
Binary Counter
Abstract Test
Can we do better
Results
Statistical Physics
Algorithmic Question
Pots Model
Computational Problems
Conclusion
Questions
Tree Evaluation
Conclusions
Taught by
Association for Computing Machinery (ACM)
