Robustness of average-case meta-complexity via pseudorandomness Article Swipe

PDF

Related Concepts

Pseudorandomness Kolmogorov complexity Robustness (evolution) Computational complexity theory Sample complexity Communication complexity Range (aeronautics) Worst-case complexity Circuit complexity Mathematics Bounded function Quantum complexity theory Average-case complexity Complexity class Computer science Discrete mathematics Theoretical computer science Algorithm Pseudorandom number generator Artificial intelligence Electronic circuit Gene Electrical engineering Materials science Mathematical analysis Physics Quantum information Quantum mechanics Chemistry Biochemistry Engineering Quantum Composite material

Rahul Ilango , Hanlin Ren , Rahul Santhanam ·

YOU? · · 2022 · Open Access · · DOI: https://doi.org/10.1145/3519935.3520051 · OA: W4281956377

We show broad equivalences in the average-case complexity of many different meta-complexity problems, including Kolmogorov complexity, time-bounded Kolmogorov complexity, and the Minimum Circuit Size Problem. These results hold for a wide range of parameters (various thresholds, approximation gaps, weak or strong average-case hardness, etc.) and complexity notions, showing the theory of meta-complexity is very *robust* in the average-case setting.