Power from Random Strings

DOI10.1137/050628994zbMath1106.68049OpenAlexW2108585502MaRDI 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

completenessKolmogorov complexityreductionsderandomizationrandomness

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (44)

On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) ⋮ Randomness, Computation and Mathematics ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ A zero-one law for RP and derandomization of AM if NP is not small ⋮ Nonuniform reductions and NP-completeness ⋮ 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 ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ 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 ⋮ Catalytic space: non-determinism and hierarchy ⋮ The Complexity of Complexity ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Non-uniform reductions ⋮ On Resource-Bounded Versions of the van Lambalgen Theorem ⋮ 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 ⋮ On the Polynomial Depth of Various Sets of Random Strings ⋮ Limits on the Computational Power of Random Strings ⋮ Avoiding simplicity is complex ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ On the computational power of random strings ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Natural Proofs versus Derandomization ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Polylog depth, highness and lowness for E ⋮ 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 hidden subgroup problem and MKTP

This page was built for publication: Power from Random Strings