Using Nondeterminism to Amplify Hardness
From MaRDI portal
Publication:5470719
DOI10.1137/S0097539705447281zbMath1096.68063OpenAlexW3021570316MaRDI QIDQ5470719
Alexander D. Healy, Emanuele Viola, Salil P. Vadhan
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539705447281
hardness amplificationaverage-case complexitynoise stabilitypseudorandom generators for space-bounded computation
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Hardness amplification within NP against deterministic algorithms, Paradigms for Unconditional Pseudorandom Generators, Query complexity in errorless hardness amplification, Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs, Complexity of hard-core set proofs, A PCP Characterization of AM, The value of help bits in randomized and average-case complexity, 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, Query Complexity in Errorless Hardness Amplification, Computational Randomness from Generalized Hardcore Sets, Direct Sum Testing
