Robustness of average-case meta-complexity via pseudorandomness
Rahul Ilango, Hanlin Ren, Rahul Santhanam
Abstract
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.
Topics & Concepts
PseudorandomnessKolmogorov complexityRobustness (evolution)Computational complexity theorySample complexityCommunication complexityRange (aeronautics)Worst-case complexityCircuit complexityMathematicsBounded functionQuantum complexity theoryAverage-case complexityComplexity classComputer scienceDiscrete mathematicsTheoretical computer scienceAlgorithmPseudorandom number generatorArtificial intelligenceElectronic circuitGeneElectrical engineeringMaterials scienceMathematical analysisPhysicsQuantum informationQuantum mechanicsChemistryBiochemistryEngineeringQuantumComposite materialComputability, Logic, AI AlgorithmsComplexity and Algorithms in GraphsCryptography and Data Security