Pseudorandomness and average-case complexity via uniform reductions
From MaRDI portal
Publication:2475578
DOI10.1007/s00037-007-0233-xzbMath1133.68023OpenAlexW1973874352MaRDI QIDQ2475578
Luca Trevisan, Salil P. Vadhan
Publication date: 11 March 2008
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-007-0233-x
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (29)
On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) ⋮ Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Time hierarchies for cryptographic function inversion with advice ⋮ Unnamed Item ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Circuit Lower Bounds for Average-Case MA ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Hardness amplification within NP against deterministic algorithms ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ The power of natural properties as oracles ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Limits on the Computational Power of Random Strings ⋮ Unnamed Item ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ In a World of P=BPP ⋮ Unnamed Item ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
This page was built for publication: Pseudorandomness and average-case complexity via uniform reductions
