Noise-tolerant learning, the parity problem, and the statistical query model

DOI10.1145/335305.335355zbMath1296.68122arXivcs/0010022MaRDI QIDQ5895204

Adam Tauman Kalai, Avrim L. Blum, Hal Wasserman

Publication date: 26 September 2014

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

Full work available at URL: https://arxiv.org/abs/cs/0010022

Mathematics Subject Classification ID

68T05: Learning and adaptive systems in artificial intelligence

Related Items

Lattice-Based SNARGs and Their Application to More Efficient Obfuscation, Learning nonsingular phylogenies and hidden Markov models, On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL, On the advantage over a random assignment, On solving LPN using BKW and variants, Implementation and analysis, The extended \(k\)-tree algorithm, Semantic security for the McEliece cryptosystem without random oracles, Unconditional lower bounds for learning intersections of halfspaces, Separating models of learning with faulty teachers, Input locality and hardness amplification, A survey on fast correlation attacks, Learning from positive and unlabeled examples, Two-Round Man-in-the-Middle Security from LPN, Cryptographic Assumptions: A Position Paper, Towards Sound Fresh Re-keying with Hard (Physical) Learning Problems, Optimization of $$\mathsf {LPN}$$ Solving Algorithms, Separating Models of Learning with Faulty Teachers