3 papers
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…
cs.CC2026
Learning, Compression, and Meta-Complexity
Halley Goldberg, Mikito Nanashima, Igor C. Oliveira
The idea that learning is closely tied to compression has long served as both a powerful principle and, at times, an informal analogy across machine learning and learning theory. H…