Hardness amplification within NP

DOI10.1016/J.JCSS.2004.01.001MaRDI QIDQ5917544zbMATH OpenOpenAlexFDO

Authors Ryan O'Donnell

Publication date 4 October 2004

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2004.01.001

zbMATH Keywords

expected biashardness amplificationmonotonenoise sensitivityNPXOR Lemma

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

• Improved hardness amplification in NP
• Using Nondeterminism to Amplify Hardness
• Using nondeterminism to amplify hardness
• Hardness Amplification Proofs Require Majority
• On uniform amplification of hardness in NP

Cites work

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• Constant depth circuits, Fourier transform, and learnability
• Hardness vs randomness
• scientific article; zbMATH DE number 4106654 (Why is no real title available?)
• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 736286 (Why is no real title available?)
• scientific article; zbMATH DE number 1500548 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Noise sensitivity of Boolean functions and applications to percolation
• Normal approximation - some recent advances
• On the Fourier spectrum of monotone functions
• On Yao's XOR-lemma
• Pseudorandom generators without the XOR lemma

Cited in

(19)

• On the (im)possibility of non-interactive correlation distillation
• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• Query complexity in errorless hardness amplification
• Using nondeterminism to amplify hardness
• On uniform amplification of hardness in NP
• On derandomization and average-case complexity of monotone functions
• A stronger LP bound for formula size lower bounds via clique constraints
• Complexity of hard-core set proofs
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• UG-hardness to NP-hardness by losing half
• Hardness Amplification Proofs Require Majority
• Using Nondeterminism to Amplify Hardness
• Submodular functions are noise stable
• Hardness amplification within NP against deterministic algorithms
• The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions
• Hardness self-amplification: simplified, optimized, and unified
• 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: Hardness amplification within NP

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