Hardness of KT characterizes parallel cryptography

DOI10.4230/LIPICS.CCC.2021.35MaRDI QIDQ6115398zbMATH OpenOpenAlexFDO

Authors Hanlin Ren, Rahul Santhanam

Publication date 12 July 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2021/14309/pdf/LIPIcs-CCC-2021-35.pdf/

zbMATH Keywords

KT complexitymeta-complexityone-way functionparallel cryptographyrandomized encodings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(12)

• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• A duality between one-way functions and average-case symmetry of information
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
• The non-uniform perebor conjecture for time-bounded Kolmogorov complexity is false
• On black-box meta complexity and function inversion
• NP-hardness of approximating meta-complexity: a cryptographic approach
• One-way functions and pKt complexity
• Lower bounds for Levin-Kolmogorov complexity
• SAT reduces to the minimum circuit size problem with a random oracle
• Kolmogorov complexity characterizes statistical zero knowledge

This page was built for publication: Hardness of KT characterizes parallel cryptography

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