A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information
Halley Goldberg, Valentine Kabanets
Abstract
We give a simplified proof of Hirahara's STOC'21 result showing that DistPH$\subseteq$AvgP would imply PH$\subseteq$DTIME[$2^{O(n \log n)}$] . The argument relies on a proof of the new result: Symmetry of Information for time-bounded Kolmogorov complexity under the assumption that NP is easy on average, which is interesting in its own right and generalizes the ``weak'' Symmetry of Information theorem from the original paper by Hirahara.