Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Asymmetry and Complexity of Nondeterministic Computations
Halley Goldberg, Jinqiao Hu, Zhenjian Lu +2
Symmetry of Information (SoI) [ZL70] is a fundamental theorem of classical Kolmogorov complexity whose status for time-bounded computation is closely related to central open proble…
cs.CC2026
The Gap Between Average-Case and Worst-Case Complexity
Halley Goldberg, Jinqiao Hu, Zhenjian Lu +2
Understanding the average-case complexity of is a central goal in complexity theory and cryptography. A necessary milestone is to understand the corresponding average…