Robustness of average-case meta-complexity via pseudorandomness

DOI10.1145/3519935.3520051MaRDI QIDQ6083613zbMATH OpenWikidataFDO

Authors Rahul Ilango, Hanlin Ren, Rahul Santhanam

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3519935.3520051

zbMATH Keywords

average-case complexitycoding theoremKolmogorov complexitymeta-complexityminimum circuit size problemone-way functions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Pseudorandomness and average-case complexity via uniform reductions
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• Strong average-case lower bounds from non-trivial derandomization
• Pseudorandom Generators in Propositional Proof Complexity
• scientific article; zbMATH DE number 7515768
• Coarse reducibility and algorithmic randomness
• Randomized complexity
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Complexity of distributions and average-case hardness
• scientific article; zbMATH DE number 7561748

Cited in

(9)

• scientific article; zbMATH DE number 7515768 (Why is no real title available?)
• One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions
• On one-way functions and sparse languages
• Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
• NP-hardness of approximating meta-complexity: a cryptographic approach
• One-way functions and pKt complexity
• Towards general-purpose program obfuscation via local mixing
• SAT reduces to the minimum circuit size problem with a random oracle
• Kolmogorov complexity characterizes statistical zero knowledge

This page was built for publication: Robustness of average-case meta-complexity via pseudorandomness

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