Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity

DOI10.1007/978-3-030-41672-0_2zbMath1440.68141OpenAlexW3007294200MaRDI QIDQ3297821

Eric W. Allender

Publication date: 20 July 2020

Published in: Complexity and Approximation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-41672-0_2

zbMATH Keywords

Kolmogorov complexitycomplexity theoryminimum circuit size problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) History of computer science (68-03)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• The new complexity landscape around circuit minimization
• Kolmogorov characterizations of complexity classes
• Kolmogorov complexity and degrees of tally sets
• On the notion of infinite pseudorandom sequences
• An information-theoretic approach to time bounds for on-line computation
• On the inference of optimal descriptions
• An excursion to the Kolmogorov random strings
• Some consequences of the existnce of pseudorandom generators
• Computational depth: Concept and applications
• Discrete logarithm and minimum circuit size
• Zero knowledge and circuit minimization
• The minimum oracle circuit size problem
• Resource-Bounded Kolmogorov Complexity Revisited
• Reductions to the set of random strings: The resource-bounded case
• Algorithmic Randomness and Complexity
• Minimum Circuit Size, Graph Isomorphism, and Related Problems
• Circuit minimization problem
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• On the Complexity of Learning Minimum Time-Bounded Turing Machines
• Randomness conservation inequalities; information and independence in mathematical theories
• Computational limitations on learning from examples
• On Languages with Very High Space-Bounded Kolmogorov Complexity
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Instance complexity
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Hardness magnification near state-of-the-art lower bounds
• Reductions to sets of low information content
• New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
• On the NP-Completeness of the Minimum Circuit Size Problem.
• Power from Random Strings
• An introduction to Kolmogorov complexity and its applications
• The non-hardness of approximating circuit size

This page was built for publication: Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity