Power from Random Strings

DOI10.1137/050628994zbMath1106.68049MaRDI QIDQ5470741

Detlef Ronneburger, Michal Koucký, Dieter van Melkebeek, Harry Buhrman, Eric W. Allender

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050628994

zbMATH Keywords

completeness; Kolmogorov complexity; reductions; derandomization; randomness

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D15: Complexity of computation (including implicit computational complexity)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, NL-printable sets and Nondeterministic Kolmogorov Complexity, Minimum Circuit Size, Graph Isomorphism, and Related Problems, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Randomness and Intractability in Kolmogorov Complexity, Hardness magnification near state-of-the-art lower bounds, Circuit lower bounds from NP-hardness of MCSP under turing reductions, The non-hardness of approximating circuit size, The power of natural properties as oracles, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), Some games on Turing machines and power from random strings, The final nail in the coffin of statistically-secure obfuscator, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Avoiding simplicity is complex, Catalytic space: non-determinism and hierarchy, Non-uniform reductions, On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \), Nonuniform reductions and NP-completeness, On the computational power of random strings, Polylog depth, highness and lowness for E, The hidden subgroup problem and MKTP, A zero-one law for RP and derandomization of AM if NP is not small, Discrete logarithm and minimum circuit size, Zero knowledge and circuit minimization, Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs, The minimum oracle circuit size problem, Cryptographic hardness under projections for time-bounded Kolmogorov complexity, Natural Proofs versus Derandomization, Randomness, Computation and Mathematics, The Complexity of Complexity, On Resource-Bounded Versions of the van Lambalgen Theorem, On the Polynomial Depth of Various Sets of Random Strings, Limits on the Computational Power of Random Strings, Minimum Circuit Size, Graph Isomorphism, and Related Problems, Unnamed Item, Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity, On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets, Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization