Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HEURISTICA :
Reports tagged with Heuristica :
TR26-253 | 13th October 2026
Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor Oliveira

The Gap Between Average-Case and Worst-Case Complexity

Understanding the average-case complexity of $\mathrm{NP}$ is a central goal in complexity theory and cryptography. A necessary milestone is to understand the corresponding average-case versus worst-case question for the polynomial hierarchy ($\mathrm{PH}$). In a celebrated result, Hirahara [Hir21] proved that if every distributional problem in $\mathrm{PH}$ is easy on average, ... more >>>




ISSN 1433-8092 | Imprint