Cryptographic hardness under projections for time-bounded Kolmogorov complexity

DOI10.1016/j.tcs.2022.10.040OpenAlexW3135228425MaRDI QIDQ2699976

Caleb Robelle, Eric W. Allender, Shuichi Hirahara, John Gouwar

Publication date: 20 April 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.10.040

zbMATH Keywords

Kolmogorov complexityinteractive proofsminimum circuit size problemworst-case to average-case reductions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the size of depth-two threshold circuits for the inner product mod 2 function
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• On the impossibility of entropy reversal, and its application to zero-knowledge proofs
• Hardness of sparse sets and minimal circuit size problem
• Discrete logarithm and minimum circuit size
• Zero knowledge and circuit minimization
• The minimum oracle circuit size problem
• Uniform derandomization from pathetic lower bounds
• Minimum Circuit Size, Graph Isomorphism, and Related Problems
• Circuit minimization problem
• A complete problem for statistical zero knowledge
• Randomness conservation inequalities; information and independence in mathematical theories
• Noninteractive Zero-Knowledge
• A polynomial restriction lemma with applications
• Hardness magnification near state-of-the-art lower bounds
• Circuit lower bounds from NP-hardness of MCSP under turing reductions
• New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
• On the NP-Completeness of the Minimum Circuit Size Problem.
• Hardness Amplification Proofs Require Majority
• Power from Random Strings
• Cryptography in $NC^0$
• On Worst‐Case to Average‐Case Reductions for NP Problems
• The non-hardness of approximating circuit size

This page was built for publication: Cryptographic hardness under projections for time-bounded Kolmogorov complexity