Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > HALLEY GOLDBERG:
All reports by Author Halley Goldberg:

TR26-290 | 14th October 2026
Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor Oliveira

Asymmetry and Complexity of Nondeterministic Computations

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 problems in complexity theory and cryptography. In a recent development, [HMO26] showed that SoI fails for $rKt$ complexity, namely in the setting of randomized computation. By ... more >>>




ISSN 1433-8092 | Imprint