On Agnostic Learning of Parities, Monomials, and Halfspaces
From MaRDI portal
Publication:3558016
DOI10.1137/070684914zbMath1198.68156OpenAlexW1968540673MaRDI QIDQ3558016
Vitaly Feldman, Parikshit Gopalan, Subhash A. Khot, Ashok Kumar Ponnuswami
Publication date: 29 April 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/7a2f79fb2f5f2a1880cabea71c93350be8e729d0
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (16)
Stronger data poisoning attacks break data sanitization defenses ⋮ Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes ⋮ Algorithmic Signaling of Features in Auction Design ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Improved approximation of linear threshold functions ⋮ On the hardness of learning intersections of two halfspaces ⋮ Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time ⋮ BKW meets Fourier new algorithms for LPN with sparse parities ⋮ A complete characterization of statistical query learning with applications to evolvability ⋮ A new column generation algorithm for logical analysis of data ⋮ Solving the learning parity with noise's open question ⋮ New Algorithms for Learning in Presence of Errors ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ Improved learning of \(k\)-parities ⋮ Cryptographic hardness for learning intersections of halfspaces ⋮ Pseudorandom Functions: Three Decades Later
This page was built for publication: On Agnostic Learning of Parities, Monomials, and Halfspaces
