Pages that link to "Item:Q1321029"
From MaRDI portal
The following pages link to \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs (Q1321029):
Displaying 50 items.
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- Pseudorandom generators for combinatorial checkerboards (Q395607) (← 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)
- Complexity of hard-core set proofs (Q451110) (← links)
- Average-case intractability vs. worst-case intractability (Q598182) (← links)
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR (Q603915) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- Hardness amplification within NP against deterministic algorithms (Q619904) (← links)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds (Q645124) (← links)
- If NP has polynomial-size circuits, then MA=AM (Q674343) (← links)
- Collapsing and separating completeness notions under average-case and worst-case hypotheses (Q693053) (← links)
- Avoiding simplicity is complex (Q693072) (← links)
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification (Q744610) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- Hardness vs randomness (Q1337458) (← links)
- Randomness vs time: Derandomization under a uniform assumption (Q1604214) (← links)
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. (Q1872705) (← links)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732) (← links)
- Uniformly hard languages. (Q1874273) (← links)
- Hard sets are hard to find (Q1961379) (← links)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games (Q2012178) (← links)
- Fourier concentration from shrinkage (Q2012185) (← links)
- Nonuniform reductions and NP-completeness (Q2158296) (← links)
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP'' is not contained in P/poly (Q2328311) (← links)
- Efficient learning algorithms yield circuit lower bounds (Q2517822) (← links)
- Circuit lower bounds from learning-theoretic approaches (Q2636410) (← links)
- On derandomizing Yao's weak-to-strong OWF construction (Q2697871) (← links)
- Natural Proofs versus Derandomization (Q2805512) (← links)
- Uniform derandomization from pathetic lower bounds (Q2941601) (← links)
- Limits on the Computational Power of Random Strings (Q3012814) (← links)
- ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS (Q3084685) (← links)
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification (Q3088109) (← links)
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More) (Q3088174) (← links)
- Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
- (Q3304139) (← links)
- (Q4638059) (← links)
- Foundations of Homomorphic Secret Sharing (Q4993284) (← links)
- (Q5002697) (← links)
- (Q5009532) (← links)
- A downward translation in the polynomial hierarchy (Q5048934) (← links)
- Randomness and Intractability in Kolmogorov Complexity (Q5091181) (← links)
- Typically-correct derandomization for small time and space (Q5091759) (← links)
- (Q5092470) (← links)
- Does Looking Inside a Circuit Help (Q5111215) (← links)
- (Q5121895) (← links)
- A combination of testability and decodability by tensor products (Q5252263) (← links)
- Erasures versus errors in local decoding and property testing (Q6074671) (← links)
- The power of natural properties as oracles (Q6116834) (← links)
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) (Q6140986) (← links)
