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.DS2024
Pairwise-Independent Contention Resolution
Anupam Gupta, Jinqiao Hu, Gregory Kehne +1
We study online contention resolution schemes (OCRSs) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-i…