Complexity I
Offered By: Association for Computing Machinery (ACM) via YouTube
Course Description
Overview
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.
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)
Related Courses
The Next Generation of InfrastructureDelft University of Technology via edX The Beauty and Joy of Computing - AP® CS Principles Part 2
University of California, Berkeley via edX Advanced Data Structures in Java
University of California, San Diego via Coursera Theory of Computation
Indian Institute of Technology Kanpur via Swayam 离散数学
Shanghai Jiao Tong University via Coursera