Pages that link to "Item:Q1604214"
From MaRDI portal
The following pages link to Randomness vs time: Derandomization under a uniform assumption (Q1604214):
Displaying 31 items.
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds (Q430845) (← links)
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma (Q451107) (← links)
- On uniformity and circuit lower bounds (Q488049) (← links)
- The size of SPP (Q596117) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification (Q744610) (← links)
- Some results on derandomization (Q1771319) (← links)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732) (← links)
- A zero-one SUBEXP-dimension law for BPP (Q1944915) (← links)
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs (Q1960516) (← links)
- Pseudorandomness and average-case complexity via uniform reductions (Q2475578) (← links)
- Efficient learning algorithms yield circuit lower bounds (Q2517822) (← links)
- Circuit lower bounds from learning-theoretic approaches (Q2636410) (← links)
- Natural proofs versus derandomization (Q2805512) (← links)
- Limits on the Computational Power of Random Strings (Q3012814) (← links)
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification (Q3088109) (← links)
- In a World of P=BPP (Q3088186) (← links)
- (Q3819053) (← links)
- Pseudodeterministic constructions in subexponential time (Q4978012) (← links)
- Fine-grained derandomization: from problem-centric to resource-centric complexity (Q5002697) (← links)
- Randomness and Intractability in Kolmogorov Complexity (Q5091181) (← links)
- Two Comments on Targeted Canonical Derandomizers (Q5098768) (← links)
- Worst-Case to Average-Case Reductions for Subclasses of P (Q5098780) (← links)
- Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace (Q5856147) (← links)
- Unions of Disjoint NP-Complete Sets (Q5892145) (← links)
- Pseudorandom generators without the XOR lemma (Q5943089) (← links)
- Easiness assumptions and hardness tests: Trading time for zero error (Q5956013) (← links)
- (Q6084358) (← links)
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) (Q6140986) (← links)
- Constructive separations and their consequences (Q6566463) (← links)
