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

DOI10.1145/335305.335355zbMath1296.68122arXivcs/0010022OpenAlexW2124407183MaRDI 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

Learning and adaptive systems in artificial intelligence (68T05)

Related Items

On solving LPN using BKW and variants, Implementation and analysis ⋮ Noisy Simon period finding ⋮ 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 ⋮ Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ A survey on fast correlation attacks ⋮ Making the BKW algorithm practical for LWE ⋮ Permuted puzzles and cryptographic hardness ⋮ Pseudorandom correlation functions from variable-density LPN, revisited ⋮ New time-memory trade-offs for subset sum -- improving ISD in theory and practice ⋮ Solving the learning parity with noise problem using quantum algorithms ⋮ Optimization of $$\mathsf {LPN}$$ Solving 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 ⋮ Correlated pseudorandomness from the hardness of quasi-abelian decoding ⋮ Input locality and hardness amplification ⋮ The extended \(k\)-tree algorithm ⋮ Separating Models of Learning with Faulty Teachers ⋮ Solving systems of linear Boolean equations with noisy right-hand sides over the reals ⋮ Learning nonsingular phylogenies and hidden Markov models ⋮ On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL ⋮ Two-Round Man-in-the-Middle Security from LPN ⋮ Cryptographic Assumptions: A Position Paper ⋮ Semantic security for the McEliece cryptosystem without random oracles ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ On the advantage over a random assignment ⋮ Separating models of learning with faulty teachers ⋮ 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 Sound Fresh Re-keying with Hard (Physical) Learning Problems ⋮ Learning from positive and unlabeled examples ⋮ Unnamed Item ⋮ Lattice-Based SNARGs and Their Application to More Efficient Obfuscation ⋮ Towards efficient LPN-based symmetric encryption

This page was built for publication: Noise-tolerant learning, the parity problem, and the statistical query model