XOR codes and sparse learning parity with noise

DOI10.1137/1.9781611975482.61MaRDI QIDQ5236245zbMATH OpenOpenAlexFDO

Authors

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975482.61

Mathematics Subject Classification ID

Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• An improved algorithm for learning sparse parities in the presence of noise
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• New Algorithms for Learning in Presence of Errors
• On noise-tolerant learning of sparse parities and related problems
• Noise-tolerant learning, the parity problem, and the statistical query model

Cited in

(6)

• BKW meets Fourier new algorithms for LPN with sparse parities
• Oblivious transfer with constant computational overhead
• Sample efficient search to decision for kLIN
• A case where a spindly two-layer linear network decisively outperforms any neural network with a fully connected input layer
• Fast pseudorandom correlation functions from sparse LPN
• Improved search-to-decision reduction for random local functions

This page was built for publication: XOR codes and sparse learning parity with noise

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236245)