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 101–200 of 602
Better Algorithms for LWE and LWR
Duc, A., Tramèr, F., & Serge Vaudenay, B. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46800-5_8 · Cited by 45
Cryptography with Constant Input Locality
Applebaum, B., Ishai, Y., & Eyal Kushilevitz, Z. (2009) · Journal of Cryptology · doi:10.1007/s00145-009-9039-0 · Cited by 45
Unconditional lower bounds for learning intersections of halfspaces
Klivans, A. R., & Sherstov, A. A. (2007) · Machine Learning · doi:10.1007/s10994-007-5010-1 · Cited by 45
Un-Trusted-HB: Security Vulnerabilities of Trusted-HB.
Frumkin, D., & Adi Shamir, Z. (2009) · Cited by 45
Open-set Label Noise Can Improve Robustness Against Inherent Label NoisePreprint
Wei, H., Tao, L., Xie, R., & An, B. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.10891 · Cited by 46
Side-Channel Analysis of Multiplications in GF(2128)
Belaïd, S., Fouque, P.-A., & Gérard, B. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45608-8_17 · Cited by 44
Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN
Yu, Y., & Zhang, J. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53018-4_9 · Cited by 44
Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications
Druk, E., & Ishai, Y. (2014) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2554797.2554815 · Cited by 43
One T Gate Makes Distribution Learning Hard
Hinsche, M., Ioannou, M., Nietner, A., Haferkamp, J., Quek, Y., Hangleiter, D., Seifert, J., Eisert, J., & Sweke, R. (2023) · Physical Review Letters · doi:10.1103/physrevlett.130.240602 · Cited by 61
GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures with Single-Bit Nonce Bias
Aranha, D. F., Fouque, P.-A., Gérard, B., Kammerer, J.-G., Tibouchi, M., & Zapalowicz, J.-C. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45611-8_14 · Cited by 41
A hybrid generative/discriminative method for semi-supervised classification
Jiang, Z., Zhang, S., & Zeng, J. (2012) · Knowledge-Based Systems · doi:10.1016/j.knosys.2012.07.020 · Cited by 41
Provable limitations of deep learningPreprint
Abbe, E. A., & Sandon, C. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.06369 · Cited by 50
Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing
Brakerski, Z., Lyubashevsky, V., Vaikuntanathan, V., & Wichs, D. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-17659-4_21 · Cited by 40
Asymptotically Efficient Lattice-Based Digital Signatures
Lyubashevsky, V., & Micciancio, D. (2017) · Journal of Cryptology · doi:10.1007/s00145-017-9270-z · Cited by 39
Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS
Guo, Q., & Johansson, T. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-92068-5_2 · Cited by 39
A guide to homomorphic encryption
Will, M. A., & Ko, R. K. L. (2015) · Elsevier eBooks · doi:10.1016/b978-0-12-801595-7.00005-7 · Cited by 38
A Practical Public Key Encryption Scheme Based on Learning Parity With Noise
Yu, Z., Gao, C.-Z., Jing, Z., Gupta, B. B., & Cai, Q. (2018) · IEEE Access · doi:10.1109/access.2018.2840119 · Cited by 38
On the Hardness of Module Learning with Errors with Short Distributions
Boudgoust, K., Jeudy, C., Roux-Langlois, A., & Wen, W. (2022) · Journal of Cryptology · doi:10.1007/s00145-022-09441-3 · Cited by 37
A complete characterization of statistical query learning with applications to evolvability
Feldman, V. (2012) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2011.12.024 · Cited by 37
Minder, L., & Sinclair, A. (2009) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973068.65 · Cited by 37
Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond.Preprint
Goldwasser, S., Kalai, Y. T., Popa, R. A., Vaikuntanathan, V., & Zeldovich, N. (2012) · IACR Cryptology ePrint Archive · Cited by 37
Learning Quantum Circuits of Some T Gates
Lai, C., & Cheng, H. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3151760 · Cited by 36
Bernstein, D. J., & Lange, T. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36140-1_10 · Cited by 37
Solving Medium-Density Subset Sum Problems in Expected Polynomial Time
Flaxman, A. D., & Przydatek, B. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31856-9_25 · Cited by 36
(2015) · Elsevier eBooks · doi:10.1016/c2014-0-00456-x · Cited by 35
On the asymptotic complexity of solving LWE
Herold, G., Kirshanova, E., & May, A. (2017) · Designs Codes and Cryptography · doi:10.1007/s10623-016-0326-0 · Cited by 35
Minaud, B., Derbez, P., Fouque, P.-A., & Karpman, P. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48800-3_1 · Cited by 34
Minder, L., & Sinclair, A. (2011) · Journal of Cryptology · doi:10.1007/s00145-011-9097-y · Cited by 34
Sherstov, A. A. (2007) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2007.11 · Cited by 34
Faster Algorithms for Solving LPN
Zhang, B., Jiao, L., & Wang, M. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49890-3_7 · Cited by 34
Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
O’Donnell, R., Wright, J., Wu, C., & Zhou, Y. (2013) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973402.120 · Cited by 33
On a Dual/Hybrid Approach to Small Secret LWE
Espitau, T., Joux, A., & Kharchenko, N. K. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-65277-7_20 · Cited by 32
On the Learnability of Fully-Connected Neural Networks
Zhang, Y., Lee, J. D., Wainwright, M. J., & Jordan, M. I. (2017) · Cited by 31
Local List-Decoding and Testing of Random Linear Codes from High Error
Kopparty, S., & Saraf, S. (2010) · SIAM Journal on Computing · doi:10.1137/100811945 · Cited by 31
On agnostic boosting and parity learning
Kalai, A. T., Mansour, Y., & Verbin, E. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374466 · Cited by 31
Self-citationOn The Power of Membership Queries in Agnostic Learning
Feldman, V. (2008) · Cited by 30
Quantum algorithms for highly non-linear Boolean functions
Rötteler, M. (2008) · Cited by 29
On the list decodability of random linear codes with large error rates
Wootters, M. K. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488716 · Cited by 29
Cryptographic Schemes Based on the ASASA Structure: Black-box, White-box, and Public-key
Biryukov, A., Bouillaguet, C., & Khovratovich, D. (2014) · Open Repository and Bibliography (University of Luxembourg) · Cited by 28
A Complete Characterization of Statistical Query Learning with Applications to Evolvability
Feldman, V. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.35 · Cited by 28
The Complexity of Public-Key Cryptography
Barak, B. (2017) · Information security and cryptography · doi:10.1007/978-3-319-57048-8_2 · Cited by 28
Analyzing the HB and HB+ Protocols in the "Large Error" Case.
Katz, J., & Smith, A. (2006) · Cited by 28
REDsec: Running Encrypted Discretized Neural Networks in Seconds
Folkerts, L. W., Gouert, C., & Tsoutsos, N. G. (2023) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2023.24034 · Cited by 28
A Fourier-Analytic Approach to Reed-Muller Decoding
Gopalan, P. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.71 · Cited by 27
FPGA Implementation of a Cryptographically-Secure PUF Based on Learning Parity with Noise
Jin, C., Herder, C. H., Ren, L., Nguyen, P. H., Fuller, B. W., Devadas, S., & van Dijk, M. (2017) · Cryptography · doi:10.3390/cryptography1030023 · Cited by 27
O’Donnell, R., & Servedio, R. A. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374450 · Cited by 27
Solving LPN Using Covering Codes
Guo, Q., Johansson, T., & Löndahl, C. (2019) · Journal of Cryptology · doi:10.1007/s00145-019-09338-8 · Cited by 27
Cryptography with Constant Input Locality
Applebaum, B. (2013) · Information security and cryptography · doi:10.1007/978-3-642-17367-7_8 · Cited by 27
Enhancing Side-Channel Analysis of Binary-Field Multiplication with Bit Reliability
Pessl, P., & Mangard, S. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-29485-8_15 · Cited by 26
Optimal Merging in Quantum $$k$$-xor and k-sum Algorithms
Naya‐Plasencia, M., & Schrottenloher, A. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45724-2_11 · Cited by 29
Razborov, A. A., & Sherstov, A. A. (2008) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.19 · Cited by 25
Prediction with a short memory
Sharan, V., Kakade, S. M., Liang, P., & Valiant, G. J. (2018) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3188745.3188954 · Cited by 27
Collision Resistant Hashing from Sub-exponential Learning Parity with Noise
Yu, Y., Zhang, J., Weng, J., Guo, C. F., & Li, X. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-34621-8_1 · Cited by 24
Efficient Authentication from Hard Learning Problems
Kiltz, E., Pietrzak, K., Venturi, D., Cash, D., & Jain, A. (2016) · Journal of Cryptology · doi:10.1007/s00145-016-9247-3 · Cited by 23
A brief survey on encrypted control: From the first to the second generation and beyond
Schlüter, N., Binfet, P., & Darup, M. S. (2023) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2023.100913 · Cited by 28
Cryptography in Constant Parallel Time
Applebaum, B. (2013) · Information security and cryptography · doi:10.1007/978-3-642-17367-7 · Cited by 23
Rivest, R. L., & Weis, S. A. (2006) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 23
Quantum-Resistant Lightweight Authentication and Key Agreement Protocol for Fog-Based Microgrids
Lu, S., & Li, X. (2021) · IEEE Access · doi:10.1109/access.2021.3058180 · Cited by 22
Quantum algorithms for attacking hardness assumptions in classical and post‐quantum cryptography
Biasse, J., Bonnetain, X., Kirshanova, E., Schrottenloher, A., & Song, F. (2022) · IET Information Security · doi:10.1049/ise2.12081 · Cited by 23
Breaking the Circuit Size Barrier for Secure Computation Under Quasi-Polynomial LPN
Couteau, G., & Meyer, P. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-77886-6_29 · Cited by 21
Randomly Punctured Reed–Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields
Alrabiah, O., Guruswami, V., & Li, R. (2024) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3618260.3649634 · Cited by 21
HELEN: A Public-Key Cryptosystem Based on the LPN and the Decisional Minimal Distance Problems
Duc, A., & Serge Vaudenay, B. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38553-7_6 · Cited by 22
On Noise-Tolerant Learning of Sparse Parities and Related Problems
Grigorescu, E., Reyzin, L., & Vempala, S. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-24412-4_32 · Cited by 21
NLHB: A non-linear Hopper-Blum protocol
Madhavan, M., Thangaraj, A., Sankarasubramanian, Y., & Viswanathan, K. (2010) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2010.5513440 · Cited by 21
Embedding Hard Learning Problems Into Gaussian Space
Klivans, A. R., & Kothari, P. K. (2014) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.approx-random.2014.793 · Cited by 24
Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN
Yu, Y., & Steinberger, J. P. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49896-5_6 · Cited by 21
Auerbach, B., Cash, D., Fersch, M., & Kiltz, E. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-63688-7_4 · Cited by 21
Guo, Q., Johansson, T., Mårtensson, E., & Stankovski, P. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70694-8_12 · Cited by 21
Learning Halfspaces and Neural Networks with Random InitializationPreprint
Zhang, Y., Lee, J. D., Wainwright, M. J., & Jordan, M. I. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.07948 · Cited by 28
A New Algorithm for Solving Ring-LPN With a Reducible Polynomial
Guo, Q., Johansson, T., & Löndahl, C. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2475738 · Cited by 20
A Coding-Theoretic Approach to Cryptanalysis
Thesis, D. (2013) · Cited by 20
Minaud, B., Derbez, P., Fouque, P.-A., & Karpman, P. (2017) · Journal of Cryptology · doi:10.1007/s00145-017-9272-x · Cited by 20
A Faster Subquadratic Algorithm for Finding Outlier Correlations
Karppa, M., Kaski, P., & Kohonen, J. (2015) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974331.ch90 · Cited by 20
Hardness of Reconstructing Multivariate Polynomials over Finite Fields
Gopalan, P., Khot, S., & Saket, R. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.37 · Cited by 20
Evolution with Drifting TargetsPreprint
Kanade, V., Valiant, L. G., & Vaughan, J. W. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1005.3566 · Cited by 20
A Framework for Efficient Adaptively Secure Composable Oblivious Transfer in the ROMPreprint
Barreto, P. S. L. M., David, B., Dowsley, R., Morozov, K., & Nascimento, A. C. A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.08256 · Cited by 20
Creating Cryptographic Challenges Using Multi-Party Computation
Buchmann, J. A., Büscher, N., Göpfert, F., Katzenbeisser, S., Krämer, J., Micciancio, D., Siim, S., van Vredendaal, C., & Walter, M. (2016) · doi:10.1145/2898420.2898422 · Cited by 20
Huth, C., Becker, D., Merchan, J. G., Duplys, P., & Güneysu, T. E. (2017) · IEEE Access · doi:10.1109/access.2017.2713835 · Cited by 19
Fast Vector Oblivious Linear Evaluation from Ring Learning with Errors
de Castro, L., Juvekar, C., & Vaikuntanathan, V. (2021) · doi:10.1145/3474366.3486928 · Cited by 19
Rötteler, M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03816-7_56 · Cited by 18
SPRING: Fast Pseudorandom Functions from Rounded Ring Products
Banerjee, A., Brenner, H., Leurent, G., Peikert, C., & Rosen, A. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46706-0_3 · Cited by 18
Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature
Applebaum, B., Ishai, Y., & Eyal Kushilevitz, Z. (2010) · Cited by 18
A Practical View of the State-of-the-Art of Lattice-Based Cryptanalysis
Mariano, A., Laarhoven, T., Correia, F. J. G., Rodrigues, M., & Falcão, G. (2017) · IEEE Access · doi:10.1109/access.2017.2748179 · Cited by 18
Average-case Hardness of RIP CertificationPreprint
Wang, T., Berthet, Q., & Plan, Y. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.09646 · Cited by 18
Computational Separation Between Convolutional and Fully-Connected NetworksPreprint
Malach, E., & Shalev‐Shwartz, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.01369 · Cited by 21
Enhancing Reliability and Security: A Configurable Poisoning PUF Against Modeling Attacks
Lin, C.-C., & Chen⋆, M.-S. (2022) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2022.3197529 · Cited by 17
Fossorier, M. P. C., Mihaljević, M. J., Imai, H., Cui, Y., & Matsuura, K. (2006) · Cited by 17
Comparison between Subfield and Straightforward Attacks on NTRU.Preprint
Kirchner, P., & Fouque, P.-A. (2016) · IACR Cryptology ePrint Archive · Cited by 17
Quantum Lock: A Provable Quantum Communication Advantage
Chakraborty, K., Doosti, M., Ma, Y., Wadhwa, C., Arapinis, M., & Kashefi, E. (2023) · Quantum · doi:10.22331/q-2023-05-23-1014 · Cited by 16
Yang, Y., Yang, Y., Chen, J., Zheng, J., & Zheng, Z. (2024) · Multimedia Tools and Applications · doi:10.1007/s11042-023-17743-2 · Cited by 16
Combinatorial Inference against Label Noise
Seo, P. H., Kim, G., & Han, B. (2019) · neural information processing systems · Cited by 16
Secure and Efficient LCMQ Entity Authentication Protocol
Li, Z., Gong, G., & Qin, Z. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2253892 · Cited by 16
A Novel Probabilistic Passive Attack on the Protocols HB and HB+
Carrijo, J., Tonicelli, R., Imai, H., & Nascimento, A. C. A. (2009) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.e92.a.658 · Cited by 16
Understanding sources of variations in flash memory for physical unclonable functions
Xu, S. Q., Yu, W.-K. S., Suh, G. E., & Kan, E. C.-C. (2014) · IEEE International Memory Workshop (IMW) · doi:10.1109/imw.2014.6849385 · Cited by 16
Hardness of Reconstructing Multivariate Polynomials over Finite Fields
Gopalan, P., Khot, S., & Saket, R. (2010) · SIAM Journal on Computing · doi:10.1137/070705258 · Cited by 16
Simulating Quantum Correlations with Finite Communication
Regev, O., & Toner, B. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.31 · Cited by 16
Feldman, V. (2016) · Encyclopedia of Algorithms · doi:10.1007/978-1-4939-2864-4_401 · Cited by 16
Liu, D., Li, N., Kim, J., & Nepal, . (2017) · IACR Cryptology ePrint Archive · Cited by 16
A survey on fast correlation attacks
Ågren, M., Löndahl, C., Hell, M., & Johansson, T. (2012) · Cryptography and Communications · doi:10.1007/s12095-012-0062-x · Cited by 15
HB+DB : Distance bounding meets human based authentication
Pagnin, E., Yang, A., Hu, Q., Hancke, G. P., & Mitrokotsa, A. (2016) · Future Generation Computer Systems · doi:10.1016/j.future.2016.05.031 · Cited by 15
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
