Power from Random Strings
From MaRDI portal
Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Recommendations
Cited in
(80)- Catalytic space: non-determinism and hierarchy
- Limits on the computational power of random strings
- Non-uniform reductions
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- Nonuniform reductions and NP-completeness
- The frequent paucity of trivial strings
- 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
- Randomness is hard
- Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity
- 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
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- On nonadaptive reductions to the set of random strings and its dense subsets
- Nonuniform reductions and NP-completeness
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- On generating independent random strings
- Avoiding simplicity is complex
- scientific article; zbMATH DE number 3974293 (Why is no real title available?)
- scientific article; zbMATH DE number 3984572 (Why is no real title available?)
- scientific article; zbMATH DE number 107775 (Why is no real title available?)
- On Languages with Very High Space-Bounded Kolmogorov Complexity
- scientific article; zbMATH DE number 1335898 (Why is no real title available?)
- On the complexity of random strings
- P-Printable Sets
- NL-printable sets and nondeterministic Kolmogorov complexity
- Minimum circuit size, graph isomorphism, and related problems
- Hardness magnification near state-of-the-art lower bounds
- Randomness and intractability in Kolmogorov complexity
- Circuit lower bounds for MCSP from local pseudorandom generators
- \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
- Hardness magnification near state-of-the-art lower bounds
- scientific article; zbMATH DE number 7561748 (Why is no real title available?)
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- scientific article; zbMATH DE number 7561759 (Why is no real title available?)
- On complexity classes and algorithmically random languages (extended abstract)
- scientific article; zbMATH DE number 7204388 (Why is no real title available?)
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- Unexpected hardness results for Kolmogorov complexity under uniform reductions
- STACS 2004
- Enumerations of the Kolmogorov function
- 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
- A duality between one-way functions and average-case symmetry of information
- NP-hardness of approximating meta-complexity: a cryptographic approach
- Constructive separations and their consequences
- On randomized reductions to the random strings
- One-tape Turing machine and branching program lower bounds for MCSP
- A direct PRF construction from Kolmogorov complexity
- On the computational power of C-random strings
- Stretching demi-bits and nondeterministic-secure pseudorandomness
- Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
- Avoiding simplicity is complex
- NP-hardness of approximating meta-complexity: a cryptographic approach
- On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
- Lower bounds for Levin-Kolmogorov complexity
- On the structure of learnability beyond \textsf{P/poly}
- One-tape Turing machine and branching program lower bounds for MCSP
- A meta-complexity theoretic approach to indistinguishability obfuscation and witness pseudo-canonicalization
- Lifting for constant-depth circuits and applications to MCSP
- An efficient coding theorem via probabilistic representations and its applications
- SAT reduces to the minimum circuit size problem with a random oracle
- Kolmogorov complexity characterizes statistical zero knowledge
- A universal uniform approximation theorem for neural networks
This page was built for publication: Power from Random Strings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470741)
