One-Way Functions and the Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
Yanyi Liu, Rafael Pass
2023年份
10被引次数
6顶会引用
问问这篇 Paper
问问你的智能体。
Lune 读过与它相关的顶会 Paper，每个回答都会注明依据哪几篇。
引用它的顶会 Paper6
- A Meta-complexity Characterization of Minimal Quantum CryptographyBruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray 等STOC 2026 · 被引用 4 次
- Optimal Coding for Randomized Kolmogorov Complexity and Its ApplicationsShuichi Hirahara, Zhenjian Lu, Mikito NanashimaFOCS 2024 · 被引用 3 次
- A Meta-complexity Characterization of Quantum CryptographyBruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray, Peter HallEUROCRYPT 2025 · 被引用 2 次
- NP-hardness of the Minimum Circuit Size Problem from Well-Studied AssumptionsShuichi Hirahara, Rahul IlangoFOCS 2025 · 被引用 1 次
- Failure of Symmetry of Information for Randomized ComputationsJinqiao Hu, Yahel Manor, Igor C. OliveiraSTOC 2026
相关 Paper
- A Duality between One-Way Functions and Average-Case Symmetry of InformationShuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima 等STOC 2023 · 被引用 9 次
- Hardness Along the Boundary: Towards One-Way Functions from the Worst-Case Hardness of Time-Bounded Kolmogorov ComplexityYanyi Liu, Rafael PassCRYPTO 2025 · 被引用 1 次
- Robustness of average-case meta-complexity via pseudorandomnessRahul Ilango, Hanlin Ren, Rahul SanthanamSTOC 2022 · 被引用 13 次
- Capturing One-Way Functions via NP-Hardness of Meta-ComplexityShuichi HiraharaSTOC 2023 · 被引用 9 次
- On One-way Functions and Kolmogorov ComplexityYanyi Liu, Rafael PassFOCS 2020 · 被引用 39 次
