YoVDO

Complexity I

Offered By: Association for Computing Machinery (ACM) via YouTube

Tags

Complexity Theory Courses Algorithms Courses Statistical Physics Courses

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 Theory
The 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