Cryptographic hardness under projections for time-bounded Kolmogorov complexity

DOI10.4230/LIPICS.ISAAC.2021.54MaRDI QIDQ6187822zbMATH OpenFDO

Authors Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

Publication date 15 January 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2021.54

zbMATH Keywords

interactive proofsKolmogorov complexityminimum circuit size problemworst-case to average-case reductions

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• On the average-case complexity of MCSP and its variants
• scientific article; zbMATH DE number 7204388
• The non-hardness of approximating circuit size
• The non-hardness of approximating circuit size

Cited in

(1)

• Cryptographic hardness under projections for time-bounded Kolmogorov complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187822)