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…
Integrity signals
Registry
Cites
Statistics
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?
Zelikman et al.'s system is not a general-purpose coding agent with the ability to work on arbitrary software engineering tasks.
“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
Zelikman et al.'s system self-improves and evaluates only on algorithmic tasks such as learning parity with noise, String Grid Distance, and 3-SAT.
“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
Cites
The Theory of Error-Correcting Codes
(1977) · North-Holland mathematical library · doi:10.1016/s0924-6509(08)x7030-8 · Cited by 10,875 · see citing works
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 · see citing works
Angluin, D., & Laird, P. D. (1988) · Machine Learning · doi:10.1023/a:1022873112823 · Cited by 839 · see citing works
Efficient noise-tolerant learning from statistical queries
Kearns, M. J. (1998) · Journal of the ACM · doi:10.1145/293347.293351 · Cited by 679 · see citing works
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 565 · see citing works
A Generalized Birthday Problem
Wagner, D. A. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45708-9_19 · Cited by 544 · see citing works
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 · see citing works
Self-citationProceedings on Advances in cryptology---CRYPTO '86
Odlyzko, A. M. (1987) · Cited by 215 · see citing works
From on-line to batch learning
Littlestone, N. (1989) · Conference on Learning Theory · doi:10.5555/93335.93365 · Cited by 121 · see citing works
Helmbold, D. P., Sloan, R. H., & Warmuth, M. K. (1992) · SIAM Journal on Computing · doi:10.1137/0221019 · Cited by 84 · see citing works
Statistical queries and faulty PAC oracles
Decatur, S. E. (1993) · Conference on Learning Theory · doi:10.1145/168304.168346 · Cited by 51 · see citing works
Specification and simulation of statistical query algorithms for efficiency and noise tolerance
Aslam, J. A., & Decatur, S. E. (1995) · Conference on Learning Theory · doi:10.1145/225298.225351 · Cited by 46 · see citing works
General Bounds on Statistical Query Learning and PAC Learning with Noise via Hypothesis Boosting
Aslam, J. A., & Decatur, S. E. (1998) · Information and Computation · doi:10.1006/inco.1998.2664 · Cited by 27 · see citing works
Specification and Simulation of Statistical Query Algorithms for Efficiency and Noise Tolerance
Aslam, J. A., & Decatur, S. E. (1998) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1558 · Cited by 24 · see citing works
On polynomial approximation to the shortest lattice vector length
Kumar, R., & Sivakumar, D. (2001) · Symposium on Discrete Algorithms · doi:10.5555/365411.365427 · Cited by 14 · see citing works
Learning in Hybrid Noise Environments Using Statistical Queries
Decatur, S. E. (1996) · Lecture notes in statistics · doi:10.1007/978-1-4612-2404-4_25 · Cited by 13 · see citing works
On the Efficiency of Noise-Tolerant PAC Algorithms Derived from Statistical Queries
Jackson, J. C. (2003) · Annals of Mathematics and Artificial Intelligence · doi:10.1023/a:1024697502780 · Cited by 13 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Trapdoors for hard lattices and new cryptographic constructions
Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374407 · Cited by 2,501 · see citing works
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060603 · Cited by 2,383 · see citing works
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2009) · Journal of the ACM · doi:10.1145/1568318.1568324 · Cited by 2,315 · see citing works
A brief introduction to weakly supervised learning
Zhou, Z.-H. (2018) · National Science Review · doi:10.1093/nsr/nwx106 · Cited by 1,899 · see citing works
Co-teaching: Robust Training of Deep Neural Networks with Extremely Noisy LabelsPreprint
Han, B., Yao, Q., Yu, X., Niu, G., Xu, M., Hu, W., Tsang, I. W.-H., & Sugiyama, M. (2018) · arXiv (Cornell University) · doi:10.5555/3327757.3327944 · Cited by 1,674 · see citing works
Predicting many properties of a quantum system from very few measurements
Huang, H.-Y., Kueng, R., & Preskill, J. (2020) · Nature Physics · doi:10.1038/s41567-020-0932-7 · Cited by 1,240 · see citing works
TFHE: Fast Fully Homomorphic Encryption Over the Torus
Chillotti, I., Gama, N., Georgieva, M., & Izabachène, M. (2019) · Journal of Cryptology · doi:10.1007/s00145-019-09319-x · Cited by 1,018 · see citing works
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898 · see citing works
CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme
Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., & Stehlé, D. (2018) · IACR Transactions on Cryptographic Hardware and Embedded Systems · doi:10.46586/tches.v2018.i1.238-268 · Cited by 893 · see citing works
On the concrete hardness of Learning with Errors
Albrecht, M. R., Player, R., & Scott, S. (2015) · Journal of Mathematical Cryptology · doi:10.1515/jmc-2015-0016 · Cited by 888 · see citing works
Authenticating Pervasive Devices with Human Protocols
Juels, A., & Weis, S. A. (2005) · Lecture notes in computer science · doi:10.1007/11535218_18 · Cited by 722 · see citing works
Better Key Sizes (and Attacks) for LWE-Based Encryption
Lindner, R., & Peikert, C. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19074-2_21 · Cited by 703 · see citing works
Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds
Chillotti, I., Gama, N., Georgieva, M., & Izabachène, M. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53887-6_1 · Cited by 692 · see citing works
Micciancio, D., & Regev, O. (2009) · Springer eBooks · doi:10.1007/978-3-540-88702-7_5 · Cited by 684 · see citing works
Combating Noisy Labels by Agreement: A Joint Training Method with Co-Regularization
Wei, H., Feng, L., Chen, X., & An, B. (2020) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr42600.2020.01374 · Cited by 649 · see citing works
Lossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. R. (2008) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 640 · see citing works
Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
Applebaum, B., Cash, D., Peikert, C., & Sahai, A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03356-8_35 · Cited by 570 · see citing works
Regev, O. (2006) · Lecture notes in computer science · doi:10.1007/11818175_8 · Cited by 499 · see citing works
Pseudorandom Functions and Lattices
Banerjee, A., Peikert, C., & Rosen, A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29011-4_42 · Cited by 483 · see citing works
PMLB: a large benchmark suite for machine learning evaluation and comparison
Olson, R. S., Cava, W. L., Orzechowski, P., Urbanowicz, R. J., & Moore, J. H. (2017) · BioData Mining · doi:10.1186/s13040-017-0154-4 · Cited by 373 · see citing works
Early-Learning Regularization Prevents Memorization of Noisy LabelsPreprint
Liu, S., Niles‐Weed, J., Razavian, N., & Fernandez‐Granda, C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.00151 · Cited by 372 · see citing works
A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
Kuperberg, G. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539703436345 · Cited by 357 · see citing works
Kasiviswanathan, S. P., Lee, H. K., Kobbi Nissim, B., Raskhodnikova, S., & Smith, A. (2008) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.27 · Cited by 349 · see citing works
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344 · see citing works
Hardness of SIS and LWE with Small Parameters
Micciancio, D., & Peikert, C. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40041-4_2 · Cited by 307 · see citing works
Simple Encrypted Arithmetic Library - SEAL v2.1
Chen, H., Laine, K., & Player, R. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70278-0_1 · Cited by 280 · see citing works
SWIFFT: A Modest Proposal for FFT Hashing
Lyubashevsky, V., Micciancio, D., Peikert, C., & Rosen, A. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-71039-4_4 · Cited by 269 · see citing works
The Learning with Errors Problem (Invited Survey)
Regev, O. (2010) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2010.26 · Cited by 265 · see citing works
New Algorithms for Learning in Presence of Errors
Arora, S., & Ge, R. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22006-7_34 · Cited by 246 · see citing works
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem.
Ding, J. (2012) · Cited by 215 · see citing works
Demonstration of quantum advantage in machine learning
Ristè, D., Silva, M. P. D., Ryan, C. A., Cross, A. W., Córcoles, A. D., Smolin, J. A., Gambetta, J. M., Chow, J. M., & Johnson, B. R. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0017-3 · Cited by 208 · see citing works
Agnostically Learning Halfspaces
Kalai, A. T., Klivans, A. R., Mansour, Y., & Servedio, R. A. (2008) · SIAM Journal on Computing · doi:10.1137/060649057 · Cited by 198 · see citing works
Self-citationParallel and Concurrent Security of the HB and HB + Protocols
Katz, J. I., & Shin, J. S. (2006) · Lecture notes in computer science · doi:10.1007/11761679_6 · Cited by 187 · see citing works
Levieil, É., & Fouque, P.-A. (2006) · Lecture notes in computer science · doi:10.1007/11832072_24 · Cited by 180 · see citing works
Differentially Private Data Release through Multidimensional Partitioning
Xiao, Y., Xiong, L., & Yuan, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15546-8_11 · Cited by 167 · see citing works
Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts
Méaux, P., Journault, A., Standaert, F., & Carlet, C. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49890-3_13 · Cited by 167 · see citing works
Open-environment machine learning
Zhou, Z. (2022) · National Science Review · doi:10.1093/nsr/nwac123 · Cited by 161 · see citing works
Lyubashevsky, V. (2005) · Lecture notes in computer science · doi:10.1007/11538462_32 · Cited by 144 · see citing works
New Results for Learning Noisy Parities and Halfspaces
Feldman, V., Gopalan, P., Khot, S., & Ponnuswami, A. K. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.51 · Cited by 142 · see citing works
Protocols for RFID tag/reader authentication
Piramuthu, S. (2007) · Decision Support Systems · doi:10.1016/j.dss.2007.01.003 · Cited by 132 · see citing works
Semantic security for the McEliece cryptosystem without random oracles
Nojima, R., Imai, H., Kobara, K., & Morozov, K. (2008) · Designs Codes and Cryptography · doi:10.1007/s10623-008-9175-9 · Cited by 122 · see citing works
Rasta: A Cipher with Low ANDdepth and Few ANDs per Bit
Dobraunig, C., Eichlseder, M., Grassi, L., Lallemand, V., Leander, G., List, E., Mendel, F., & Rechberger, C. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-96884-1_22 · Cited by 117 · see citing works
Learnability of Quantum Neural Networks
Du, Y., Hsieh, M.-H., Liu, T., You, S., & Tao, D. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.040337 · Cited by 114 · see citing works
Learning nonsingular phylogenies and hidden Markov models
Mossel, E., & Roch, S. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060645 · Cited by 110 · see citing works
Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise
Jain, A., Krenn, S., Pietrzak, K., & Tentes, A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-34961-4_40 · Cited by 109 · see citing works
Biryukov, A., Bouillaguet, C., & Khovratovich, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45611-8_4 · Cited by 108 · see citing works
A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial SpacePreprint
Regev, O. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0406151 · Cited by 107 · see citing works
Hyperparameter Optimization: A Spectral ApproachPreprint
Hazan, E., Klivans, A. R., & Yang, Y. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.00764 · Cited by 107 · see citing works
Complexity theoretic limitations on learning halfspaces
Daniely, A. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897520 · Cited by 103 · see citing works
Parallel and Concurrent Security of the HB and HB+ Protocols
Katz, J. I., Shin, J. S., & Smith, A. (2010) · Journal of Cryptology · doi:10.1007/s00145-010-9061-2 · Cited by 102 · see citing works
Lattice Decoding Attacks on Binary LWE
Bai, S., & Galbraith⋆, S. D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-08344-5_21 · Cited by 101 · see citing works
On the complexity of the BKW algorithm on LWE
Albrecht, M. R., Cid, C., Faugère, J., Fitzpatrick, R., & Perret, L. (2013) · Designs Codes and Cryptography · doi:10.1007/s10623-013-9864-x · Cited by 101 · see citing works
An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
Kirchner, P., & Fouque, P.-A. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47989-6_3 · Cited by 99 · see citing works
HB and Related Lightweight Authentication Protocols for Secure RFID Tag/Reader Authentication
Piramuthu, S. (2006) · Cited by 98 · see citing works
Efficient Authentication from Hard Learning Problems
Kiltz, E., Pietrzak, K., Cash, D., Jain, A., & Venturi, D. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20465-4_3 · Cited by 96 · see citing works
Kunisky, D., Wein, A. S., & Bandeira, A. S. (2022) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-030-97127-4_1 · Cited by 96 · see citing works
Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encryption
Canetti, R., Chen, Y., Reyzin, L., & Rothblum, R. D. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-78381-9_4 · Cited by 92 · see citing works
A Secure Human-Computer Authentication Scheme
Hopper, N., & Blum, M. (2000) · doi:10.21236/ada382135 · Cited by 90 · see citing works
Schoppmann, P., Gascón, A., Reichert, L., & Raykova, M. (2019) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3319535.3363228 · Cited by 88 · see citing works
Cryptography from Learning Parity with Noise
Pietrzak, K. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-27660-6_9 · Cited by 88 · see citing works
Herder, C. H., Ren, L., van Dijk, M., Yu, M.-D., & Devadas, S. (2016) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2016.2536609 · Cited by 88 · see citing works
Lightweight Security and Privacy Preserving Scheme for Smart Grid Customer-Side Networks
Abdallah, A. R., & Shen, X. (2015) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2015.2463742 · Cited by 86 · see citing works
A survey on the complexity of learning quantum states
Anshu, A., & Arunachalam, S. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00662-4 · Cited by 88 · see citing works
How (Not) to Instantiate Ring-LWE
Peikert, C. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-44618-9_22 · Cited by 82 · see citing works
How to Encrypt with the LPN Problem
Gilbert, H., Robshaw, M. J. B., & Seurin, Y. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70583-3_55 · Cited by 81 · see citing works
Agnostically Learning Halfspaces
Kalai, A. T., Klivans, A. R., Mansour, Y., & Servedio, R. A. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.13 · Cited by 81 · see citing works
Self-citationAlgorithmic Aspects of Machine Learning
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177 · Cited by 81 · see citing works
Quantum learning robust against noise
Cross, A. W., Smith, G., & Smolin, J. A. (2015) · Physical Review A · doi:10.1103/physreva.92.012327 · Cited by 80 · see citing works
Lapin: An Efficient Authentication Protocol Based on Ring-LPN
Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., & Pietrzak, K. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-34047-5_20 · Cited by 79 · see citing works
Cognition-Driven Structural Prior for Instance-Dependent Label Transition Matrix Estimation
Zhang, R., Cao, Z., Yang, S., Si, L., Sun, H., Xu, L., & Sun, F. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2023.3347633 · Cited by 77 · see citing works
Instance-Dependent Label-Noise Learning with Manifold-Regularized Transition Matrix Estimation
Cheng, D., Liu, T., Ning, Y., Wang, N., Han, B., Niu, G., Gao, X., & Sugiyama, M. (2022) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52688.2022.01613 · Cited by 75 · see citing works
Reliably Learning the ReLU in Polynomial TimePreprint
Goel, S., Kanade, V., Klivans, A. R., & Thaler, J. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.10258 · Cited by 75 · see citing works
Cryptography in radio frequency identification and fair exchange protocols
Avoine, G. (2005) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5075/epfl-thesis-3407 · Cited by 72 · see citing works
Razborov, A. A., & Sherstov, A. A. (2010) · SIAM Journal on Computing · doi:10.1137/080744037 · Cited by 72 · see citing works
On Agnostic Learning of Parities, Monomials, and Halfspaces
Feldman, V., Gopalan, P., Khot, S., & Ponnuswami, A. K. (2009) · SIAM Journal on Computing · doi:10.1137/070684914 · Cited by 69 · see citing works
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas
Valiant, G. J. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.27 · Cited by 69 · see citing works
Buchmann, J. A., Göpfert, F., Player, R., & Wunderer, T. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-31517-1_2 · Cited by 68 · see citing works
From average case complexity to improper learning complexity
Daniely, A., Linial, N., & Shalev‐Shwartz, S. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591820 · Cited by 66 · see citing works
Pessl, P., Bruinderink, L. G., & Yarom, Y. (2017) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3133956.3134023 · Cited by 65 · see citing works
Learning nonsingular phylogenies and hidden Markov models
Mossel, E., & Roch, S. (2006) · The Annals of Applied Probability · doi:10.1214/105051606000000024 · Cited by 64 · see citing works
Security Parallels between People and Pervasive Devices
Weis, S. A. (2005) · IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops) · doi:10.1109/percomw.2005.72 · Cited by 64 · see citing works
Fossorier, M. P. C., Mihaljević, M. J., Imai, H., Cui, Y., & Matsuura, K. (2006) · Lecture notes in computer science · doi:10.1007/11941378_5 · Cited by 63 · see citing works
Coded-BKW: Solving LWE Using Lattice Codes
Guo, Q., Johansson, T., & Stankovski, P. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47989-6_2 · Cited by 63 · see citing works
Valiant, G. J. (2015) · Journal of the ACM · doi:10.1145/2728167 · Cited by 62 · see citing works
Evolvability from learning algorithms
Feldman, V. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374465 · Cited by 57 · see citing works
Algorithms for the approximate common divisor problem
Galbraith⋆, S. D., Gebregiyorgis, S. W., & Murphy, S. P. (2016) · LMS Journal of Computation and Mathematics · doi:10.1112/s1461157016000218 · Cited by 57 · see citing works
O’Donnell, R., & Servedio, R. A. (2011) · SIAM Journal on Computing · doi:10.1137/090756466 · Cited by 55 · see citing works
Gama, N., Izabachène, M., Nguyễn, P. Q., & Xie, X. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49896-5_19 · Cited by 54 · see citing works
Sherstov, A. A. (2008) · Computational Complexity · doi:10.1007/s00037-008-0242-4 · Cited by 54 · see citing works
Learning-with-errors problem is easy with quantum samples
Grilo, A. B., Kerenidis, I., & Zijlstra, T. (2019) · Physical Review A · doi:10.1103/physreva.99.032314 · Cited by 53 · see citing works
Review of error correction for PUFs and evaluation on state-of-the-art FPGAs
Hiller, M., Kürzinger, L., & Sigl, G. (2020) · Journal of Cryptographic Engineering · doi:10.1007/s13389-020-00223-w · Cited by 53 · see citing works
Solving LPN Using Covering Codes
Guo, Q., Johansson, T., & Löndahl, C. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45611-8_1 · Cited by 52 · see citing works
Complexity theoretic limitations on learning DNF'sPreprint
Daniely, A., & Shalev‐Shwartz, S. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1404.3378 · Cited by 52 · see citing works
ProMix: Combating Label Noise via Maximizing Clean Sample Utility
Xiao, R., Dong, Y., Wang, H., Feng, L., Wu, R., Chen, G., & Zhao, J. (2023) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2023/494 · Cited by 51 · see citing works
Weakly Supervised Adversarial Learning for 3D Human Pose Estimation from Point Clouds
Zhang, Z., Hu, L., Deng, X., & Xia, S. (2020) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2020.2973076 · Cited by 51 · see citing works
Lightweight Cryptographic Authentication in Passive RFID-Tagged Systems
Piramuthu, S. (2008) · IEEE Transactions on Systems Man and Cybernetics Part C (Applications and Reviews) · doi:10.1109/tsmcc.2007.913918 · Cited by 50 · see citing works
Lazy Modulus Switching for the BKW Algorithm on LWE
Albrecht, M. R., Faugère, J., Fitzpatrick, R., & Perret, L. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-54631-0_25 · Cited by 49 · see citing works
Improved Algorithms for the Approximate k-List Problem in Euclidean Norm
Herold, G., & Kirshanova, E. (2017) · Lecture notes in computer science · doi:10.1007/978-3-662-54365-8_2 · Cited by 48 · see citing works
Pseudorandom Functions: Three Decades Later
Bogdanov, A., & Rosen, A. (2017) · Information security and cryptography · doi:10.1007/978-3-319-57048-8_3 · Cited by 47 · see citing works
$$\mathsf {Rubato}$$: Noisy Ciphers for Approximate Homomorphic Encryption
Ha, J., Kim, S., Lee, B., Lee, J., & Son, M. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-06944-4_20 · Cited by 45 · see citing works
- 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
