Halley Goldberg

According to our database, Halley Goldberg authored at least 7 papers between 2022 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of four.

2026

Non-Levin NP-Hardness of Implicit MCSP and PAC Learning under Few Assumptions.

Halley Goldberg, Mandar Juvekar, Valentine Kabanets

Electron. Colloquium Comput. Complex., 2026

2025

Synergies Between Complexity Theory and Nondeterministic Kolmogorov Complexity.

Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2025

Witness Encryption and NP-Hardness of Learning.

Halley Goldberg, Valentine Kabanets

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity.

Halley Goldberg, Valentine Kabanets

Proceedings of the Approximation, 2024

2023

Improved Learning from Kolmogorov Complexity.

Halley Goldberg, Valentine Kabanets

Proceedings of the 38th Computational Complexity Conference, 2023

2022

A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information.

Halley Goldberg, Valentine Kabanets

Electron. Colloquium Comput. Complex., 2022

Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira

Proceedings of the 37th Computational Complexity Conference, 2022