Pseudorandomness and average-case complexity via uniform reductions
From MaRDI portal
Publication:2475578
DOI10.1007/s00037-007-0233-xzbMath1133.68023MaRDI 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
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Relations and equivalences between circuit lower bounds and karp-lipton theorems, Randomness and Intractability in Kolmogorov Complexity, Unnamed Item, Unnamed Item, 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, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, Hardness amplification within NP against deterministic algorithms, Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification, Time hierarchies for cryptographic function inversion with advice, On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \), Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, Circuit lower bounds from learning-theoretic approaches, Limits on the Computational Power of Random Strings, Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification, In a World of P=BPP, Unnamed Item, Circuit Lower Bounds for Average-Case MA, On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets
