Using Nondeterminism to Amplify Hardness

DOI10.1137/S0097539705447281MaRDI QIDQ5470719zbMATH OpenOpenAlexFDO

Authors Alexander D. Healy, Emanuele Viola, Salil 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

average-case complexityhardness amplificationnoise stabilitypseudorandom generators for space-bounded computation

Mathematics Subject Classification ID

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

Recommendations

• Using nondeterminism to amplify hardness
• Hardness amplification within NP against deterministic algorithms
• Hardness amplification within NP
• Hardness amplification in proof complexity
• On the Complexity of Hardness Amplification
• On uniform amplification of hardness in NP
• On the Amount of Nondeterminism and the Power of Verifying
• scientific article; zbMATH DE number 1500525
• Counterexamples to hardness amplification beyond negligible
• scientific article; zbMATH DE number 2081099

Cited in

(25)

• The value of help bits in randomized and average-case complexity
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• A PCP characterization of AM
• 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
• Using nondeterminism to amplify hardness
• On uniform amplification of hardness in NP
• On the Complexity of Hardness Amplification
• Complexity of hard-core set proofs
• Amplification with one NP oracle query
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• Direct sum testing
• Impossibility Results on Weakly Black-Box Hardness Amplification
• Hardness amplification within NP
• (Nondeterministic) hardness vs. non-malleability
• Paradigms for Unconditional Pseudorandom Generators
• Hardness amplification within NP against deterministic algorithms
• Hardness self-amplification: simplified, optimized, and unified
• Unprovability of strong complexity lower bounds in bounded arithmetic
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Regularization of low error PCPs and an application to MCSP
• Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
• Improved hardness amplification in NP
• Query complexity in errorless hardness amplification

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470719)