Explore the intricacies of average-case complexity in the polynomial hierarchy (PH) through the lens of worst-case meta-complexity in this 22-minute IEEE conference talk. Delve into two key mysteries of complexity theory as Shuichi Hirahara from the National Institute of Informatics presents the main theorem, comparing worst-case and average-case complexity. Examine efficiently samplable distributions and the landscape of average-case complexity. Investigate variants of MINKT, including MINKTA, and their implications. Address open questions on meta-complexity and its relationship to average-case complexity. Discover the corollary of errorless hardness amplification for PH, and conclude with a summary and thought-provoking open question in this advanced exploration of computational complexity theory.
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity
Overview
Syllabus
Intro
Two mysteries of complexity theory
Main Theorem
Worst-case versus Average-case complexity
Efficiently Samplable Distribution
Landscape of Average-case Complexity
Outline
Variants of MINKT MINKTA: an A-oracle version of MINKT Input
Open Questions on Meta-Complexity
Meta-Complexity versus Average-Case Complexity
Corollary Errorless hardness amplification for PH
Summary and an Open Question
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
-
Is it Easier to Prove Statements that are Guaranteed to be True?
-
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
-
Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits
-
Hardness Magnification for All Sparse NP Languages
-
The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs
-
Tree-Depth and the Formula Complexity of Subgraph Isomorphism
