Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Complexity Theory III

Association for Computing Machinery (ACM) via YouTube

Overview

Explore advanced concepts in complexity theory through this 39-minute conference talk from STOC 2020. Delve into topics such as minimal circuits, the High Maintenance Theorem, probabilistic formulas, and subexponential formulas. Examine new developments in the field, including explicit obstructions and polynomials with high pockets. Gain insights into the coin problem and its implications for circuit complexity. Engage with thought-provoking questions and interpretations of recent results in this cutting-edge presentation from the Association for Computing Machinery (ACM).

Syllabus

Intro
Motivation Animation
Middle Circuits
New Development
Questions
Motivation
Minimal Circuit
High Maintenance Theorem
probabilistic formulas
subexponential formulas
interpreting the results
Explicit obstruction
Polynomials with the high pocket
The main lemma
The coin problem

Taught by

Association for Computing Machinery (ACM)

Reviews

Start your review of Complexity Theory III

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.