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

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

Hal Wasserman, Adam Tauman Kalai, Avrim L. Blum

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

Unnamed Item, 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, Solving the learning parity with noise problem using quantum algorithms, A non-heuristic approach to time-space tradeoffs and optimizations for BKW, Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms, Correlated pseudorandomness from expand-accumulate codes, On solving LPN using BKW and variants, Implementation and analysis, The extended \(k\)-tree algorithm, Noisy Simon period finding, Semantic security for the McEliece cryptosystem without random oracles, Unconditional lower bounds for learning intersections of halfspaces, Separating models of learning with faulty teachers, Exploring crypto dark matter: new simple PRF candidates and their applications, Solving systems of linear Boolean equations with noisy right-hand sides over the reals, Input locality and hardness amplification, On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem, Dummy shuffling against algebraic attacks in white-box implementations, Breaking the circuit size barrier for secure computation under quasi-polynomial LPN, Towards efficient LPN-based symmetric encryption, Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN, Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes, Making the BKW algorithm practical for LWE, Permuted puzzles and cryptographic hardness, 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