The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Noise-tolerant learning, the parity problem, and the statistical query model
Abstract
We describe a slightly subexponential time algorithm for learning parity functions in the presence of random classification noise, a problem closely related to several cryptographic and coding problems. Our algorithm runs in polynomial time for the case of parity functions that depend on only the first O (log n log log n ) bits of input, which provides the first known instance of an efficient noise-tolerant algorithm for a concept class that is not learnable in the Statistical Query model of Kearns [1998]. Thus, we demonstrate that the set of problems learnable in the statistical query model is a strict subset of those problems learnable in the presence of noise in the PAC model.In coding-theory terms, what we give is a poly( n )-time algorithm for decoding linear k × n codes in the presence of random noise for the case of k = c log n log log n for some c > 0. (The case of k = O (log n ) is trivial since one can just individually check each of the 2 k possible messages and choose the one that yields the closest codeword.)A natural extension of the statistical query model is to allow queries about statistical properties that involve t -tuples of examples, as opposed to just single examples. The second result of this article is to show that any class of functions learnable (strongly or weakly) with t -wise queries for t = O (log n ) is also weakly learnable with standard unary queries. Hence, this natural extension to the statistical query model does not increase the set of wea…
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Again, this is not a general-purpose coding agent with the ability to e.g.work on arbitrary software engineering tasks, and as such, it self-improves and evaluates and only on algorithmic tasks such as learning parity with noise (Blum et al., 2003), String Grid Distance, and 3-SAT.”
From A Self-Improving Coding Agent (2025) · cites this paper as Blum et al., 2003
In the citing paper
“Again, this is not a general-purpose coding agent with the ability to e.g.work on arbitrary software engineering tasks, and as such, it self-improves and evaluates and only on algorithmic tasks such as learning parity with noise (Blum et al., 2003), String Grid Distance, and 3-SAT.”
From A Self-Improving Coding Agent (2025) · cites this paper as Blum et al., 2003
Citations
Cites
The Theory of Error-Correcting Codes
(1977) · North-Holland mathematical library · doi:10.1016/s0924-6509(08)x7030-8 · Cited by 10,891
Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
Littlestone, N. (1988) · Machine Learning · doi:10.1023/a:1022869011914 · Cited by 1,514
Angluin, D., & Laird, P. D. (1988) · Machine Learning · doi:10.1023/a:1022873112823 · Cited by 839
Efficient noise-tolerant learning from statistical queries
Kearns, M. J. (1998) · Journal of the ACM · doi:10.1145/293347.293351 · Cited by 679
A sieve algorithm for the shortest lattice vector problem
Ajtai, M., Kumar, R., & Sivakumar, D. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380857 · Cited by 579
A Generalized Birthday Problem
Wagner, D. A. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45708-9_19 · Cited by 544
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Blum, A. L., Furst, M., Jackson, J. C., Kearns, M. J., Mansour, Y., & Rudich, S. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195147 · Cited by 253
Self-citationProceedings on Advances in cryptology---CRYPTO '86
Odlyzko, A. M. (1987) · Cited by 215
From on-line to batch learning
Littlestone, N. (1989) · Conference on Learning Theory · doi:10.5555/93335.93365 · Cited by 121
Helmbold, D. P., Sloan, R. H., & Warmuth, M. K. (1992) · SIAM Journal on Computing · doi:10.1137/0221019 · Cited by 84
Cited by
Sorted by citations
Items 501–600 of 602
HB+ protocol-based Smart OTP Authentication
Shin, J. S. (2015) · 정보보호학회논문지 · doi:10.13089/jkiisc.2015.25.5.993
(2009) · Chapman & Hall/CRC cryptography and network security · doi:10.1201/9781420070033.ch13
On the security and efficiency of encryption
Cash, C. D. (2009) · SMARTech Repository (Georgia Institute of Technology)
Bela, S., & Fouque, P.-A. (2014)
GPGPU Acceleration of SAT Algorithm with Propagation Routine Parallelization
Kang, H. (2016) · The Journal of the Korean Institute of Information and Communication Engineering · doi:10.6109/jkiice.2016.20.10.1919
Lecture 24: Hardness Assumptions
Karp, J. (2013)
Post-quantum key exchange based on ring-LWE
Heesch, V. M. M. (2016)
Alekseev, E. K., Oshkin, I. B., Popov, V. O., & Smyshlyaev, S. V. (2017) · Дискретная математика · doi:10.4213/dm1401
Simple Analysis of Key Recovery Attack Against LWE
Yasuda, M. (2017) · Mathematics for industry · doi:10.1007/978-981-10-5065-7_12
Quantum Learning Algorithms and Post-Quantum CryptographyPreprint
Poremba, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1712.09289
Learning Mixtures of Product Distributions via Higher Multilinear Moments.Preprint
Chen, S., & Moitra, A. (2018) · arXiv (Cornell University)
Wootters, M. K. (2014) · Deep Blue (University of Michigan)
Cryptographic Primitives from Physical Variables
Hammouri, G. (2009) · Digital WPI
On Lattices, Codes and Regev{'}s Cryptosystem
Pancheva, K. (2007)
On the Relation Between Security Models for HB-like Symmetric Key Authentication Protocols
Zhang, M. (2019) · Lecture notes in networks and systems · doi:10.1007/978-3-030-12385-7_63
Cuong, N. V., Ho, L. S. T., & Dinh, V. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1406.3166
An MQ/Code Cyptosystem Proposal
Schulman, L. J. (2013) · CaltechAUTHORS (California Institute of Technology)
Practical Period Finding on IBM Q - Quantum Speedups in the Presence of Errors.Preprint
May, A., Schlieper, L., & Schwinger, J. (2019) · arXiv (Cornell University)
Alekseychuk, A. N., Koniushok, S. M., & Поремський, М. В. (2020) · Cybernetics and Systems Analysis · doi:10.1007/s10559-020-00220-1
Tensor Decompositions: Algorithms
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.004
Security Estimates of a Ring-Lwe Symmetric Cryptosystem Against Chosen Plaintext Attack
Ігнатенко, С. М. (2020) · Cybernetics and Systems Analysis · doi:10.1007/s10559-020-00248-3
Generalized Learning Problems and Applications to Non-Commutative Cryptography.
Baumslag, G., Fazio, N., Nicolosi, A. R., Shpilrain, V., & Skeith, W. E. (2011)
Algorithms for the Approximate Common Divisor Problem.Preprint
Galbraith⋆, S. D., Gebregiyorgis, S. W., & Murphy, S. P. (2016) · IACR Cryptology ePrint Archive
The Concrete Complexity of LWE without Gaussian Sampling
Qian, X., Liu, J., Gu, C., & Zheng, Y. (2020) · International Conference on Mathematics and Artificial Intelligence (ICMAI) · doi:10.1145/3395260.3395281
Design, Analysis, and Optimization of Isogeny-Based Key Establishment Protocols
LeGrow, J. T. (2020) · UWSpace (University of Waterloo)
Robust Learning under Strong Noise via SQsPreprint
Anagnostides, I., Gouleakis, T., & Marashian, A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.09106
BKW Algorithm Solve Fault-Tolerant Equations
王, 艺. (2020) · Advances in Applied Mathematics · doi:10.12677/aam.2020.912262
Huang, J. B., Miao, W., Zhang, M., Zhang, L., Zhang, L., & Yang, S. (2020) · doi:10.1145/3445815.3445862
Generation and Analysis of Feature-Dependent Pseudo Noise for Training Deep Neural Networks
Kamabattula, S., Musini, K. N., Namazi, B., Sankaranarayanan, G., & Devarajan, V. (2021) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/smc52423.2021.9658883
CPA/CCA2-secure PKE with squared-exponential DFR from low-noise LPN
Xu, S., Li, X., Qian, H., & Chen, K. (2021) · Theoretical Computer Science · doi:10.1016/j.tcs.2021.06.025
Boolean Ring Cryptographic Equation Solving
Murphy, S. P., Paterson, M. B., & Swart, C. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-81652-0_10
Yang, Y., Yang, Y., Chen, J., Zheng, J., & Zheng, Z. (2020) · arXiv (Cornell University)
Горбенко, І. Д., Качко, О. Г., Потій, О. В., Alekseychuk, A., Gorbenko, Y. I., Yesina, M. V., Стельник, І. В., & Ponomar, V. (2021) · Radiotekhnika · doi:10.30837/rt.2021.2.205.01
Security estimates of the NTRUCipher and NTRUCipher+ encryption schemes against BKW-attack
Matiyko, A. (2021) · Physico-mathematical modelling and informational technologies · doi:10.15407/fmmit2021.33.028
LABELNET: Recovering Noisy Labels
Ghiassi, A., Birke, R., Han, R., & Chen, L. Y. (2021) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn52387.2021.9533562
Applying Fully Homomorphic Encryption: Practices and Problems
Chen, Y. (2021) · UWSpace (University of Waterloo)
Improved learning of k-parities
Bhattacharyya, A., Gadekar, A., & Rajgopal, N. (2020) · Theoretical Computer Science · doi:10.1016/j.tcs.2020.08.025
Cao, Z. (2012) · CRC Press eBooks · doi:10.1201/b14302-9
Review on Learning Parity with Noise based cloud computing
(2020) · International Journal of Emerging Trends in Engineering Research · doi:10.30534/ijeter/2020/368102020
Computationally Efficient Mutual Entity Authentication in Wireless Sensor Networks
Li, Z., & Gong, G. (2010) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-642-11723-7_13
Learning quantum circuits of T -depth one
Lai, C., & Cheng, H. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834452
Exploiting Vulnerabilities of HB-MP
Carrijo, J., & Tonicelli, R. (2009) · doi:10.5753/sbseg.2009.20619
Morais, E., & Dahab, R. (2012) · doi:10.5753/sbc.9464.5.4
Calibrating Learning Parity with Noise Authentication for Low-Resource Devices
Tan, T. G., Soh, D. W., & Zhou, J. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-15777-6_2
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.002
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.011
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.007
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.009
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.010
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.006
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.001
Feldman, V. (2008) · Encyclopedia of Algorithms · doi:10.1007/978-0-387-30162-4_401
Learning with Errors Public Key Cryptosystem with Its Security
Zheng, Z., Tian, K., Zhang, Y., & Lu, Y. (2023) · Journal of Information Security · doi:10.4236/jis.2023.141003
A Heuristic Algorithm for LPN Decoding with Improved Memory and Time EfficiencyPreprint
Yin, S., & Min, J. (2023) · Research Square · doi:10.21203/rs.3.rs-2669767/v1
A reduction from an LWE problem to maximum independent set problems
Kawano, Y. (2023) · Scientific Reports · doi:10.1038/s41598-023-34366-7
Alekseychuk, A. N., & Ігнатенко, С. М. (2018) · Radiotekhnika · doi:10.30837/rt.2018.2.193.03
Natural robustness of machine learning in the open world
Wei, H. (2023) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/166625
Alogrithms for the ACD Problem and Cryptanalysis of ACD-based FHE schemes, RevisitedPreprint
Ran, Y., Pan, Y., & Wang, L. (2023) · Preprints.org · doi:10.20944/preprints202306.0712.v1
Alogrithms for the ACD Problem and Cryptanalysis of ACD-based FHE schemes, RevisitedPreprint
Ran, Y., Pan, Y., & Wang, L. (2023) · Preprints.org · doi:10.20944/preprints202306.0712.v2
Star-Specific Key-Homomorphic PRFs From Learning With Linear Regression
Sehrawat, V. S., Yeo, F. Y., & Vassilyev, D. (2023) · IEEE Access · doi:10.1109/access.2023.3294844
On the LWE Cryptosystem with More General Disturbance
Zheng, Z., & Kun, T. (2023) · Financial Mathematics and Fintech · doi:10.1007/978-981-99-2366-3_8
Collaborative Extreme Noise Classifier: A Multi-Network Approach Based Extreme Noise ClassificationPreprint
Guo, Z., Chen, C., Jiang, Z., & Wang, L. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4571141
Light-HHB: A Lighter Version of HHB for Resource-Constrained IoT Devices. Signature
Ka, A. K. (2023) · International Journal on Cryptography and Information Security · doi:10.5121/ijcis.2023.13402
Alekseychuk, A. N., & Shevchuk, O. (2023) · Radiotekhnika · doi:10.30837/rt.2023.4.215.03
An iterative correction method for practically LPN solving
Kang, M. K., Jiao, L., Li, Y., & Wang, M. (2024) · Information Sciences · doi:10.1016/j.ins.2024.121080
On Sample Reuse Methods for Answering k-wise Statistical Queries
Reyzin, L., & Tu, D. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-63735-3_8
A Key-Recovery Attack on the LCMQ Authentication Protocol
Nguyen, V. H., Johansson, T., & Guo, Q. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619211
Noisy Label Learning Based on Weighted Neighborhood Consistency
Rong, Q., Zhang, L., Yuan, L., Ding, X., & Li, G. (2024) · Lecture notes in computer science · doi:10.1007/978-981-97-7244-5_4
Quadripartite: Tackle Noisy Labels by Better Utilizing Uncertain Samples
Cui, X., Liang, X., Cao, C., Shi, G., & El-haddar, N. (2024) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn60899.2024.10651073
Golowich, N., Moitra, A., & Rohatgi, D. (2024) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs61266.2024.00117 · Cited by 9
Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems
Koch, C., Strassle, C., & Tan, L.-Y. (2024) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs61266.2024.00114
MALAI: ML-Based Attack on Learning with Error Problem
Sri, M. S., Yadav, C. S., Sanyashi, T., & Singh, V. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-80020-7_23
Memory-Efficient BKW Algorithm for Solving the LWE Problem
Wei, Y. J., Bi, L., Lu, X., & Wang, K. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-91823-0_11
Tripartite: Tackling Realistic Noisy Labels with More Precise Partitions
Yu, L., Liang, X., Cao, C., Yao, L., & Liu, X. (2025) · Sensors · doi:10.3390/s25113369
An improved BKW algorithm on the learning with rounding problem
Yu, W., Bi, L., Wang, K., & Lu, X. (2025) · Cybersecurity · doi:10.1186/s42400-024-00339-0
On sample reuse methods for answering k-wise statistical queries
Reyzin, L., & Tu, D. (2025) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/s10472-025-09994-6
Noise-tolerant Learning, the Parity problem, and the Statistical Query model
Blum, A. L., Kalai, A. T., & Wasserman, H. (2003) · KiltHub Repository · doi:10.1184/r1/6607733
Self-citationSample Efficient Search to Decision for kLIN
Bogdanov, A., Rosen, A., & Tan, K. Z. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-01855-7_7
On Wagner’s k-Tree Algorithm Over Integers
Lin, H., & Vasudevan, P. N. (2025) · Lecture notes in computer science · doi:10.1007/978-981-95-5018-0_16
Post-quantum Cryptography from Quantum Stabilizer Decoding
Lu, J. Z., Poremba, A., Quek, Y., & Ramkumar, A. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-35398-6_6 · Cited by 1
Authentication and encryption protocols : design, attacks and algorithmic improvements
Maimuţ, D. (2015) · theses.fr (ABES) · doi:10.70675/a4c4e8d2z5e4cz4eafzbf6bzfb9b77e3cfb7
Classical and quantum cryptanalysis for Euclidean lattices and subset sums
Shen, Y. (2021) · theses.fr (ABES) · doi:10.70675/c36a63dbz469ez406azba4fza2fd2c7ca09b
Optimizing Post-Quantum Cryptographic Algorithms for Resource-Constrained Devices
Nevuri, S. C. R. (2026) · International Symposium on Digital Forensics and Security (ISDFS) · doi:10.1109/isdfs69419.2026.11459080
Clip-Driven Zero-Shot Learning with Ambiguous Labels
Fan, J., Li, J., Yan, X., Zhong, X., Lü, W., & Huang, L. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11462279
Superposition Attacks Against LPN-Based Authentication Protocols
Cid, C. D., Elkouss, D., & Goulão, M. (2026) · IACR Communications in Cryptology · doi:10.62056/abhey7n4e
A Framework for Chiplet Authentication During Post-Stacking Test
Suzano, J., Philippe, A., Abouzeid, F., Roche, P., & Natale, G. D. (2026) · IEEE International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS) · doi:10.1109/ddecs69233.2026.11520976
Optical Kernel Machine With Programmable Nonlinearity
Han, S., Xia, F., Gigan, S., Loureiro, B., & Cao, H. W. (2026) · Laser & Photonics Review · doi:10.1002/lpor.202503155 · Cited by 1
Learning with Alternating Moduli, Arora-Ge over Composite Moduli, and Weak PRFs
Chen, Y., Ji, L., & Li, W. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-35377-1_7
Dishonest-Majority Secure Computation via PIR-Authenticated Multiplication Triples
Boyle, E., Gilboa, N., Hamilis, M., Ishai, Y., & Nof, A. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-35418-1_15
A Lightweight Post-Quantum Authentication and Key Agreement scheme for Constrained IoTPreprint
Tchapgnouo, H. B., Ciss, A. A., Ari, A. A. A., & Faye, B. L. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.7321282
Pinpointing Super-Quadratic Quantum Enumeration Speedups
Schubert, C., Paskarbeit, N., Kramer, M. J., Seifert, J., & Margraf, M. (2026) · ACM Conference on Post-Quantum and Quantum-based Security · doi:10.1145/3839338.3857257
Metadata
- Authors
- Blum, A., Kalai, A., & Wasserman, H.
- Affiliations
- Carnegie Mellon University (US)
- Venue
- Journal of the ACM
- Published
- 2003-07
- Volume
- 50
- Issue
- 4
- Pages
- 506-519
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2065151783
- Cited by
- 598
- References
- 17
- Citations by year
- 2026: 15 · 2025: 23 · 2024: 27 · 2023: 36 · 2022: 31 · 2021: 35 · 2020: 54 · 2019: 29 · 2018: 34 · 2017: 35 · 2016: 32 · 2015: 28 · 2014: 28 · 2013: 28 · 2012: 29
- FWCI
- 9.23
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Journal of the ACM (publishedVersion)
- KiltHub Repository (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Keywords
- noise-tolerant learning, parity function, statistical query model, PAC learning, subexponential algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
