Explore cutting-edge research in computational complexity theory through this 22-minute conference talk presented at the Association for Computing Machinery (ACM). Delve into the Minimum Circle Size Problem and its implications for hardness magnification. Examine previous results and discover new findings in the field. Learn about probabilistic formulas, quantification of randomization, and restrictions. Understand the Shrinkage Theorem and its application to parity proofs. Conclude by considering open problems and future directions in computational complexity research.
Sharp Threshold Results for Computational Complexity
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
Introduction
Minimum Circle Size Problem
Hardness Magnification
Previous Results
New Results
Probabilistic Formulas
Quantify the Randomization
Restrictions
Shrinkage Theorem
Parity Proof
Open Problems
Taught by
Association for Computing Machinery (ACM)
