Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity

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.

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