Using Nondeterminism to Amplify Hardness

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

zbMATH Keywords

hardness amplificationaverage-case complexitynoise stabilitypseudorandom generators for space-bounded computation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (13)

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

This page was built for publication: Using Nondeterminism to Amplify Hardness