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 401–500 of 602
Optimal Hitting Sets for Combinatorial Shapes
Bhaskara, A., Desai, D., & Srinivasan, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32512-0_36 · Cited by 2
On the Complexity of the LWR-Solving BKW Algorithm
Okada, H., Takayasu, A., Fukushima, K., Kiyomoto, S., & Takagi, T. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-12146-4_13 · Cited by 2
Message Authentication Codes Against Related‐Key Attacks Under LPN and LWE
Nan, C., & Shengli, L. (2021) · Chinese Journal of Electronics · doi:10.1049/cje.2021.05.011 · Cited by 2
Hardness of SIS and LWE with Small Parameters
Micciancio, D., & Peikert, C. (2013) · Cited by 2
Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
Dinur, I., Keller, N., & Klein, O. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs52979.2021.00017 · Cited by 2
Tensor Decompositions: Applications
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.005 · Cited by 2
Revisiting lightweight authentication protocols based on hard learning problems
Rizomiliotis, P., & Gritzalis, S. (2013) · ACM Conference on Security and Privacy in Wireless and Mobile Networks (WiSec) · doi:10.1145/2462096.2462118 · Cited by 2
Revisiting the Security of Qian et al.’s Revised Tree-$$\hbox {LSHB}^+$$ Protocol
Li, X., Xu, J. M., & Zhang, Z. (2019) · Wireless Personal Communications · doi:10.1007/s11277-019-06164-w · Cited by 2
LPN-based Device Authentication Using Resistive Memory
Arafin, M. T., Shen, H., Tehranipoor, M. M., & Qu, G. (2019) · ACM Great Lakes Symposium on VLSI (GLSVLSI) · doi:10.1145/3299874.3317970 · Cited by 2
On learning finite-state quantum sources
Juba, B. (2012) · Quantum Information and Computation · doi:10.26421/qic12.1-2-7 · Cited by 2
Specifications and improvements of LPN solving algorithms
Jiao, L. (2019) · IET Information Security · doi:10.1049/iet-ifs.2018.5448 · Cited by 2
TrustNet: Learning from Trusted Data Against (A)symmetric Label Noise
Ghiassi, A., Birke, R., & Chen, L. Y. (2021) · IEEE/ACM International Conference on Big Data Computing, Applications and Technologies (BDCAT) · doi:10.1145/3492324.3494166 · Cited by 2
Inverse problems in approximate uniform generationPreprint
De, A., Diakonikolas, I., & Servedio, R. A. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1211.1722 · Cited by 2
Some Notes on Code-Based Cryptography
Löndahl, C. (2014) · Lund University Publications (Lund University) · doi:10.13140/rg.2.1.1831.3047 · Cited by 2
New constructions of cryptographic pseudorandom functions
Banerjee, A. (2015) · SMARTech Repository (Georgia Institute of Technology) · Cited by 2
Markov models on trees: Reconstruction and applications
Roch, S. (2007) · Cited by 2
Cyclotomic Polynomials in Ring-LWE Homomorphic Encryption Schemes
Mukherjee, T. (2016) · RIT Scholar Works (Rochester Institute of Technology) · Cited by 2
On learning linear functions from subset and its applications in quantum computingPreprint
Ivanyos, G., Prakash, A., & Sántha, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.09660 · Cited by 2
QActor: On-line Active Learning for Noisy Labeled Stream DataPreprint
Younesian, T., Zhao, Z., Ghiassi, A., Birke, R., & Chen, L. Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.10399 · Cited by 2
ExpertNet: Adversarial Learning and Recovery Against Noisy LabelsPreprint
Ghiassi, A., Birke, R., Han, R., & Chen, L. Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.05305 · Cited by 2
When Hardness of Approximation Meets Hardness of LearningPreprint
Malach, E., & Shalev‐Shwartz, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.08059 · Cited by 2
Robeyns, M., Szummer, M., & Aitchison, L. (2025) · arXiv · doi:10.48550/arxiv.2504.15228 · Cited by 117
Error-Free Lattice-Based Key Encapsulation Mechanism Based on Ring-LWE
Tan, C. H., & Prabowo, T. F. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-70881-8_11 · Cited by 1
A Ring-LWE-based digital signature inspired by Lindner–Peikert scheme
Sharafi, J., & Daghigh, H. (2022) · Journal of Mathematical Cryptology · doi:10.1515/jmc-2021-0013 · Cited by 1
Instantiating the Hash-then-evaluate paradigm: Strengthening PRFs, PCFs, and OPRFs
Brzuska, C., Couteau, G., Egger, C., Karanko, P., & Meyer, P. (2025) · Cryptography and Communications · doi:10.1007/s12095-025-00825-3 · Cited by 1
Slightly Sublinear Trapdoor Hash Functions and PIR from Low-Noise LPN
Abram, D., Malavolta, G., & Roy, L. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-12287-2_10 · Cited by 1
Hardness Amplification beyond Boolean Functions
Shimizu, N., & Yasunaga, K. (2026) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3798129.3800838 · Cited by 1
Zero-Shot Learning with Noisy Labels
Pan, Z., Tang, L., & Pan, Z. (2023) · Procedia Computer Science · doi:10.1016/j.procs.2023.08.049 · Cited by 1
Zero-Knowledge Proofs from Learning Parity with Noise: Optimization, Verification, and Application
Haines, T., Mosaheb, R., Müller, J., & Reetika (2025) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf64896.2025.00010 · Cited by 1
Wang, Y., Pang, H., Qin, Y. H., Wei, S., & Zhao, Y. (2025) · Neural Networks · doi:10.1016/j.neunet.2025.107464 · Cited by 1
VCR: Fast Private Set Intersection with Improved VOLE and CRT-Batching
Jing, W., Chen, X., Chen, X., Dong, Y., Yang, Y., & Liu, Q. (2025) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom66490.2025.00219 · Cited by 1
Partial label zero-shot learning with semantic mining and instance–label alignment
Fan, J., Li, J., Huang, L., Gan, M., & Chen, C. L. P. (2026) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2026.114854 · Cited by 1
Venturi, D. (2012) · Unitext · doi:10.1007/978-88-470-2481-6_9 · Cited by 1
Solving the learning parity with noiseʼs open question
Suttichaya, V., & Bhattarakosol, P. (2013) · Information Processing Letters · doi:10.1016/j.ipl.2013.04.016 · Cited by 1
On the Robustness of Learning Parity with Noise
Yao, N., Yu, Y., Li, X., & Gu, D. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-50011-9_8 · Cited by 1
Session-HB: Improving the Security of HB $$^{+}$$ with a Session Key Exchange
Ka, A. K. (2018) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-319-72965-7_19 · Cited by 1
On the Hardness of Learning Parity with Noise over Rings
Zhao, S., Yu, Y., & Zhang, J. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-01446-9_6 · Cited by 1
Ka, A. K. (2014) · Cited by 1
Lattice Decoding Attacks on Binary LWE.
Bai, S., & Galbraith⋆, S. D. (2013) · Cited by 1
Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise
Jain, A., Krenn, S., Pietrzak, K., & Tentes, A. (2012) · Cited by 1
On the Hardness of Sparsely Learning Parity with Noise
Yan, D., Liu, H., Zhao, S., & Yu, Y. (2021) · The Computer Journal · doi:10.1093/comjnl/bxab027 · Cited by 1
Shortest Vectors in Lattices of Bai-Galbraith’s Embedding Attack on the LWR Problem
Uemura, S., Fukushima, K., Kiyomoto, S., Kudo, M., & Takagi, T. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-85987-9_2 · Cited by 1
On the Complexity of the LWR-Solving BKW Algorithm
Okada, H., Takayasu, A., Fukushima, K., Kiyomoto, S., & Takagi, T. (2019) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.2019cip0022 · Cited by 1
Self-Augmentation Based on Noise-Robust Probabilistic Model for Noisy Labels
Park, B. W., Park, S., & Kwon, J. (2022) · IEEE Access · doi:10.1109/access.2022.3219810 · Cited by 1
Sample-size-reduction of quantum states for the noisy linear problem
Jeong, K. (2023) · Annals of Physics · doi:10.1016/j.aop.2022.169215 · Cited by 1
Shandilya, S. K., Datta, A., & Nagar, A. K. (2023) · Studies in computational intelligence · doi:10.1007/978-981-99-7081-0_3 · Cited by 1
Tackling Instance-Dependent Label Noise with Class Rebalance and Geometric Regularization
Cao, S., Ruan, J., Dong, B., & Shi, B. (2024) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3637528.3671707 · Cited by 1
Optimizing $c$-sum BKW and Faster Quantum Variant for LWE
Cao, J., Cheng, Q., & Weng, J. (2024) · IACR Communications in Cryptology · doi:10.62056/a6qj5w7sf · Cited by 1
Reyzin, L. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.9020 · Cited by 1
Hardness Estimation of LWE via Band Pruning.
Aono, Y., Phong, L. T., & Wang, L. (2015) · Cited by 1
Average-case analysis for combinatorial problems
FRIEZE, A. M., & Flaxman, A. D. (2006) · Cited by 1
Security Analysis of the Qian et al. Protocol: A Revised Tree-LSHB+ Protocol
Lei, M., Li, H., Liu, W., & Jin, D. (2017) · Wireless Personal Communications · doi:10.1007/s11277-017-4225-0 · Cited by 1
On the Hardness of Sparsely Learning Parity with Noise
Liu, H., Yan, D., Yu, Y., & Zhao, S. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-68637-0_16 · Cited by 1
Improved Learning of k-Parities
Bhattacharyya, A., Gadekar, A., & Rajgopal, N. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-94776-1_45 · Cited by 1
Pseudorandom Functions and Lattices.
Banerjee, A., Peikert, C., & Rosen, A. (2011) · Cited by 1
Obstacles to Depth Compression of Neural Networks
Burstein, W., & Wilmes, J. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-61616-8_9 · Cited by 1
Горбенко, І. Д., Олексійчук, А. М., Качко, О. Г., Горбенко, Ю. І., Єсіна, М. В., & Kandii, S. (2020) · Radiotekhnika · doi:10.30837/rt.2020.3.202.01 · Cited by 1
On the Complexity of Learning a Class Ratio from Unlabeled Data
Fish, B., & Reyzin, L. (2020) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.12013 · Cited by 1
BKW-attack on NTRUCIPHER and NTRUCIPHER+ enctyption schemes
Matiyko, A. (2020) · Collection Information technology and security · doi:10.20535/2411-1031.2020.8.2.222599 · Cited by 1
Reusable garbled circuits and succinct functional encryption
Goldwasser, S., Kalai, Y. T., Popa, R. A., Vaikuntanathan, V., & Zeldovich, N. (2013) · Cited by 1
An improved algorithm for learning sparse parities in the presence of noise
Yan, D., Yu, Y., Liu, H., Zhao, S., & Zhang, J. (2021) · Theoretical Computer Science · doi:10.1016/j.tcs.2021.04.026 · Cited by 1
Bernstein, D. J., & Lange, T. (2012) · Cited by 1
Predicting the Concrete Security of LWE Against the Dual Attack Using Binary Search
Li, S., Lu, X., Zhang, J., Li, B., & Bi, L. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-88052-1_16 · Cited by 1
Compact lossy and all-but-one trapdoor functions from lattice
Cheng, L., Wu, Q., & Zhao, Y. (2017) · ICST Transactions on Security and Safety · doi:10.4108/eai.28-12-2017.153517 · Cited by 1
The Hardware Design and Implementation of a Key Exchange Protocol for Low-cost IoT Devices
(2019) · International Journal of Recent Technology and Engineering (IJRTE) · doi:10.35940/ijrte.b1016.0782s619 · Cited by 1
Adventures in crypto dark matter: attacks, fixes and analysis for weak pseudorandom functions
Cheon, J. H., Cho, W., Kim, J. H., & Kim, J. (2022) · Designs Codes and Cryptography · doi:10.1007/s10623-022-01071-x · Cited by 1
Attacks on the Firekite Cipher
Johansson, T., Meier, W., & Nguyen, V. H. (2022) · IACR Transactions on Symmetric Cryptology · doi:10.46586/tosc.v2022.i3.191-216 · Cited by 1
Extracting Computational Entropy and Learning Noisy Linear Functions
Lee, C.-J., Lu, C.-J., & Tsai, S. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2158897 · Cited by 1
Extracting Computational Entropy and Learning Noisy Linear Functions
Lee, C.-J., Lu, C.-J., & Tsai, S. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02882-3_34 · Cited by 1
Efficient Authentication, Node Clone Detection, and Secure Data Aggregation for Sensor Networks
Li, Z. (2011) · UWSpace (University of Waterloo) · Cited by 1
New Algorithms for Solving LPN.Preprint
Zhang, B., & Gong, X. (2017) · IACR Cryptology ePrint Archive · Cited by 1
Dataset Of Experimental Measurements For "Demonstration Of Quantum Advantage In Machine Learning"
Ristè, D., Silva, M. P. D., Ryan, C. A., Cross, A. W., Corcoles, A. D., Smolin, J. A., Gambetta, J., Chow, J. M., & Johnson, B. (2017) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.268731 · Cited by 1
Lattice-Based Signature from Key Consensus.Preprint
Cheng, L., Gong, B., & Zhao, Y. (2018) · IACR Cryptology ePrint Archive · Cited by 1
Some algorithms for learning with errors
Fitzpatrick, R. (2014) · Cited by 1
On the Complexity of Learning from Label ProportionsPreprint
Fish, B., & Reyzin, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.03515 · Cited by 1
Handling Noisy Labels via One-Step Abductive Multi-Target Learning.Preprint
Yang, Y., Yang, Y., Chen, J., Zheng, J., & Zheng, Z. (2020) · arXiv (Cornell University) · Cited by 1
On the Power of Differentiable Learning versus PAC and SQ LearningPreprint
Abbe, E. A., Kamath, P., Malach, E., Sandon, C., & Srebro, N. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.04190 · Cited by 1
Security of the pseudorandom number generators and implementations of public key signature schemes
Zapalowicz, J.-C. (2014) · doi:10.70675/d9deb716zc90az4d5bz932ez04461d525ddd · Cited by 1
Linear algebra algorithms for cryptography
Delaplace, C. (2018) · doi:10.70675/ff8472bbz9d29z4e19za4d6z01d0f17e0fee · Cited by 1
Lattice algorithms and lattice-based cryptography
Kharchenko, N. K. (2020) · doi:10.70675/a477cda1z1f32z481ezbe0fzcadc18756bf0 · Cited by 1
Statistical Query Learning (1998; Kearns)
Feldman, V. (2014) · Encyclopedia of Algorithms · doi:10.1007/978-3-642-27848-8_401-2
Towards Efficient Lattice-Based Cryptography
Lindner, R. (2011) · Technischen Universität Darmstadt · doi:10.26083/tuprints-00002387
A reduction from LWE problem to dihedral coset problemPreprint
Li, F., Bao, W., Fu, X.-Q., Zhang, Y., & Li, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.3769
Security Flaws in Two RFID Lightweight Authentication Protocols
Shaohui, W. (2011) · Lecture notes in electrical engineering · doi:10.1007/978-3-642-21762-3_19
Some Recent Results on Local Testing of Sparse Linear Codes
Kopparty, S., & Saraf, S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16367-8_26
Venturi, D. (2012) · Unitext · doi:10.1007/978-88-470-2481-6_11
Security problems of systems of extremely weak devices
Klonowski, M. (2011) · Annales Universitatis Mariae Curie-Sklodowska sectio AI – Informatica · doi:10.2478/v10065-011-0015-6
MapReduce Platform for Parallel Machine Learning on Large-scale Dataset
Yanase, T., Hiroki, K., Itoh, A., & Yanai, K. (2011) · Transactions of the Japanese Society for Artificial Intelligence · doi:10.1527/tjsai.26.621
A Secure Technique Design for Privacy Protection in RFID System
Oh, G.-O., & Park, M.-O. (2010) · Journal of the Korea Society of Computer and Information · doi:10.9708/jksci.2010.15.8.107
HELEN: a Public-key Cryptosystem Based on the LPN Problem (Extended Abstract)
Duc, A., & Serge Vaudenay, B. (2012) · Infoscience (Ecole Polytechnique Fédérale de Lausanne)
Intractability results for some computational problems
Khot, S., & Ponnuswami, A. K. (2008)
Bringing Theory Closer to Practice in Post-quantum and Leakage-resilient Cryptography
Duc, A. (2015) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5075/epfl-thesis-6807
Security proofs in number theoretic cryptography
Aggarwal, D. (2012) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-a-007242748
An LPN-Problem-Based Lightweight Authentication Protocol for Wireless Communications
Chang, Y., & Lai, Y. (2009) · International Conference on Availability, Reliability and Security (ARES) · doi:10.1109/ares.2009.33
Solving the LPN problem in cube-root timePreprint
Wagner, U. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1201.4725
Efficient Learning Algorithms with Limited Information.
De, A. (2013) · eScholarship (California Digital Library)
Implementable privacy for rfid systems
Evans, D., & Nohl, K. (2009)
Detection of Planted Solutions for Flat Satisfiability ProblemsPreprint
Berthet, Q., & Ellenberg, J. S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.06144
Intractability results for problems in computational learning and approximation
Saket, R. (2009) · SMARTech Repository (Georgia Institute of Technology)
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
