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
Information TheoryThe Chinese University of Hong Kong via Coursera Intro to Computer Science
University of Virginia via Udacity Analytic Combinatorics, Part I
Princeton University via Coursera Algorithms, Part I
Princeton University via Coursera Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera