Pages that link to "Item:Q2475578"
From MaRDI portal
The following pages link to Pseudorandomness and average-case complexity via uniform reductions (Q2475578):
Displayed 26 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)
- Hardness amplification within NP against deterministic algorithms (Q619904) (← links)
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification (Q744610) (← links)
- Time hierarchies for cryptographic function inversion with advice (Q843601) (← links)
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) (Q2120065) (← links)
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP'' is not contained in P/poly (Q2328311) (← links)
- Circuit lower bounds from learning-theoretic approaches (Q2636410) (← 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)
- Circuit Lower Bounds for Average-Case MA (Q3194723) (← links)
- On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets (Q3297825) (← links)
- (Q3304157) (← links)
- (Q5002697) (← links)
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization (Q5080481) (← links)
- Randomness and Intractability in Kolmogorov Complexity (Q5091181) (← links)
- Relations and equivalences between circuit lower bounds and karp-lipton theorems (Q5091782) (← links)
- (Q5092470) (← links)
- (Q5121895) (← links)
- Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma (Q5130843) (← links)
- (Q6084353) (← links)
- (Q6084358) (← links)
- Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? (Q6113106) (← links)
- The power of natural properties as oracles (Q6116834) (← links)