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
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
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
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
A brief introduction to weakly supervised learning
Zhou, Z.-H. (2018) · National Science Review · doi:10.1093/nsr/nwx106 · Cited by 1,899
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
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
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
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898
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 959
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
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
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
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
Micciancio, D., & Regev, O. (2009) · Springer eBooks · doi:10.1007/978-3-540-88702-7_5 · Cited by 684
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
Lossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. R. (2008) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 640
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 581
Regev, O. (2006) · Lecture notes in computer science · doi:10.1007/11818175_8 · Cited by 499
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
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
Early-Learning Regularization Prevents Memorization of Noisy LabelsPreprint
Liu, S., Weed, J., Razavian, N., & Fernandez‐Granda, C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.00151 · Cited by 385
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
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 373
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
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
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 287
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
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
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
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem.
Ding, J. (2012) · Cited by 215
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
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
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
Levieil, É., & Fouque, P.-A. (2006) · Lecture notes in computer science · doi:10.1007/11832072_24 · Cited by 180
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 169
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
Open-environment machine learning
Zhou, Z. (2022) · National Science Review · doi:10.1093/nsr/nwac123 · Cited by 162
Lyubashevsky, V. (2005) · Lecture notes in computer science · doi:10.1007/11538462_32 · Cited by 144
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
Protocols for RFID tag/reader authentication
Piramuthu, S. (2007) · Decision Support Systems · doi:10.1016/j.dss.2007.01.003 · Cited by 132
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
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
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 127
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
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
Biryukov, A., Bouillaguet, C., & Khovratovich, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45611-8_4 · Cited by 112
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
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
Complexity theoretic limitations on learning halfspaces
Daniely, A. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897520 · Cited by 115
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
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
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
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
HB and Related Lightweight Authentication Protocols for Secure RFID Tag/Reader Authentication
Piramuthu, S. (2006) · Cited by 98
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
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
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
A Secure Human-Computer Authentication Scheme
Hopper, N., & Blum, M. (2000) · doi:10.21236/ada382135 · Cited by 90
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 93
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
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
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
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 126
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
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
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
Self-citationAlgorithmic Aspects of Machine Learning
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177 · Cited by 81
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
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
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 78
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
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 85
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
Razborov, A. A., & Sherstov, A. A. (2010) · SIAM Journal on Computing · doi:10.1137/080744037 · Cited by 82
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
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
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
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 70
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
Learning nonsingular phylogenies and hidden Markov models
Mossel, E., & Roch, S. (2006) · The Annals of Applied Probability · doi:10.1214/105051606000000024 · Cited by 64
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
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
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
Valiant, G. J. (2015) · Journal of the ACM · doi:10.1145/2728167 · Cited by 62
Evolvability from learning algorithms
Feldman, V. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374465 · Cited by 57
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
O’Donnell, R., & Servedio, R. A. (2011) · SIAM Journal on Computing · doi:10.1137/090756466 · Cited by 55
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
Sherstov, A. A. (2008) · Computational Complexity · doi:10.1007/s00037-008-0242-4 · Cited by 54
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
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
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
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
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 76
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
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
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
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
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
$$\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 50
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
