Hardness amplification within NP

DOI10.1145/509907.510015zbMath1192.68300OpenAlexW2124619161MaRDI QIDQ5901049

Ryan O'Donnell

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.510015

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

Gaussian bounds for noise correlation of functions ⋮ Learning intersections and thresholds of halfspaces ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ A PCP Characterization of AM ⋮ The value of help bits in randomized and average-case complexity ⋮ On the noise sensitivity of monotone functions ⋮ Computational Randomness from Generalized Hardcore Sets ⋮ Learning DNF from random walks ⋮ Direct Sum Testing

This page was built for publication: Hardness amplification within NP