ECCC-Report TR22-007https://eccc.weizmann.ac.il/report/2022/007Comments and Revisions published for TR22-007en-usFri, 14 Jan 2022 04:52:14 +0200
Paper TR22-007
| A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information |
Valentine Kabanets,
Halley Goldberg
https://eccc.weizmann.ac.il/report/2022/007We 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.Fri, 14 Jan 2022 04:52:14 +0200https://eccc.weizmann.ac.il/report/2022/007