The following pages link to Power from Random Strings (Q5470741):
Displayed 44 items.
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- Avoiding simplicity is complex (Q693072) (← links)
- Catalytic space: non-determinism and hierarchy (Q1702851) (← links)
- Non-uniform reductions (Q1959376) (← links)
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) (Q2120065) (← links)
- Nonuniform reductions and NP-completeness (Q2158296) (← links)
- On the computational power of random strings (Q2271990) (← links)
- Polylog depth, highness and lowness for E (Q2304528) (← links)
- The hidden subgroup problem and MKTP (Q2330111) (← links)
- A zero-one law for RP and derandomization of AM if NP is not small (Q2389331) (← links)
- Discrete logarithm and minimum circuit size (Q2404611) (← links)
- Zero knowledge and circuit minimization (Q2407082) (← links)
- Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs (Q2407103) (← links)
- The minimum oracle circuit size problem (Q2410683) (← links)
- Cryptographic hardness under projections for time-bounded Kolmogorov complexity (Q2699976) (← links)
- Natural Proofs versus Derandomization (Q2805512) (← links)
- Randomness, Computation and Mathematics (Q2904405) (← links)
- The Complexity of Complexity (Q2973719) (← links)
- On Resource-Bounded Versions of the van Lambalgen Theorem (Q2988817) (← links)
- On the Polynomial Depth of Various Sets of Random Strings (Q3010430) (← links)
- Limits on the Computational Power of Random Strings (Q3012814) (← links)
- Minimum Circuit Size, Graph Isomorphism, and Related Problems (Q3176189) (← links)
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity (Q3297821) (← links)
- On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets (Q3297825) (← links)
- (Q3304139) (← links)
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization (Q3380367) (← links)
- NL-printable sets and Nondeterministic Kolmogorov Complexity (Q4924524) (← links)
- Minimum Circuit Size, Graph Isomorphism, and Related Problems (Q4993283) (← links)
- (Q5028364) (← links)
- Randomness and Intractability in Kolmogorov Complexity (Q5091181) (← links)
- (Q5091189) (← links)
- (Q5091223) (← links)
- Hardness magnification near state-of-the-art lower bounds (Q5091779) (← links)
- (Q5092470) (← links)
- Circuit lower bounds from NP-hardness of MCSP under turing reductions (Q5092477) (← links)
- (Q5092482) (← links)
- (Q5111269) (← links)
- (Q5121893) (← links)
- (Q5121895) (← links)
- The non-hardness of approximating circuit size (Q5918358) (← links)
- The power of natural properties as oracles (Q6116834) (← links)
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) (Q6140986) (← links)
- Some games on Turing machines and power from random strings (Q6149034) (← links)
- The final nail in the coffin of statistically-secure obfuscator (Q6161431) (← links)