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 201–300 of 602
Using HB Family of Protocols for Privacy-Preserving Authentication of RFID Tags in a PopulationPreprint
Halevi, T., Saxena, N., & Halevi, S. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0907.1227 · Cited by 15
Learning to Collaborate in Markov Decision ProcessesPreprint
Radanović, G., Devidze, R., Parkes, D. C., & Singla, A. K. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.08029 · Cited by 15
On the Efficiency of Provably Secure NTRU
Cabarcas, D., Weiden, P., & Buchmann, J. A. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11659-4_2 · Cited by 14
Garbling XOR Gates “For Free” in the Standard Model
Applebaum, B. (2015) · Journal of Cryptology · doi:10.1007/s00145-015-9201-9 · Cited by 14
A PAC Framework for Aggregating Agents’ Judgments
Zhang, H., & Conitzer, V. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.33012237 · Cited by 14
Learning classical readout quantum PUFs based on single-qubit gates
Pirnay, N., Pappa, A., & Seifert, J. (2022) · Quantum Machine Intelligence · doi:10.1007/s42484-022-00073-1 · Cited by 14
Neural-shadow quantum state tomography
Wei, V., Coish, W. A., Ronagh, P., & Muschik, C. A. (2024) · Physical Review Research · doi:10.1103/physrevresearch.6.023250 · Cited by 18
Generalized Learning Problems and Applications to Non-commutative Cryptography
Baumslag, G., Fazio, N., Nicolosi, A. R., Shpilrain, V., & Skeith, W. E. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-24316-5_23 · Cited by 14
Statistical Queries and Statistical Algorithms: Foundations and ApplicationsPreprint
Reyzin, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.00557 · Cited by 47
Estimating Instance-dependent Label-noise Transition Matrix using DNNs.Preprint
Yang, S., Yang, E., Han, B., Liu, Y., Xu, M. G., Niu, G., & Liu, T. (2021) · arXiv (Cornell University) · Cited by 14
A Parametrical Model for Instance-Dependent Label Noise
Yang, S., Wu, S., Yang, E., Han, B., Liu, Y., Xu, M. G., Niu, G., & Liu, T. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2023.3301876 · Cited by 13
Adventures in Crypto Dark Matter: Attacks and Fixes for Weak Pseudorandom Functions
Cheon, J. H., Cho, W., Kim, J. H., & Kim, J. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-75248-4_26 · Cited by 13
On McEliece-Type Cryptosystems Using Self-Dual Codes With Large Minimum Weight
Mariot, L., Picek, S., & Yorgova, R. (2023) · IEEE Access · doi:10.1109/access.2023.3271767 · Cited by 13
Quantum Hardness of Learning Shallow Classical Circuits
Arunachalam, S., Grilo, A. B., & Sundaram, A. (2021) · SIAM Journal on Computing · doi:10.1137/20m1344202 · Cited by 13
Hardness of Learning Halfspaces with Massart Noise.Preprint
Diakonikolas, I., & Kane, D. M. (2020) · arXiv (Cornell University) · Cited by 13
Reduction from Sparse LPN to LPN, Dual Attack 3.0
Carrier, K., Debris-Alazard, T., Meyer-Hilfiger, C., & Tillich, J. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-58754-2_11 · Cited by 12
On Iterative Collision Search for LPN and Subset Sum
Devadas, S., Ren, L., & Xiao, H. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70503-3_24 · Cited by 12
On the Hardness of PAC-learning Stabilizer States with Noise
Gollakota, A., & Liang, D. (2022) · Quantum · doi:10.22331/q-2022-02-02-640 · Cited by 12
Zheng, Z., Tian, K., & Liu, F. (2022) · Financial Mathematics and Fintech · doi:10.1007/978-981-19-7644-5 · Cited by 12
DyGen: Learning from Noisy Labels via Dynamics-Enhanced Generative Modeling
Zhuang, Y., Yu, Y., Kong, L., Chen, X., & Zhang, C. (2023) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3580305.3599318 · Cited by 14
Robustness of Physical Layer Security Primitives Against Attacks on Pseudorandom Generators
Vaidyanathaswami, R., & Thangaraj, A. (2014) · IEEE Transactions on Communications · doi:10.1109/tcomm.2014.012514.130280 · Cited by 12
Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time
Karppa, M., Kaski, P., Kohonen, J., & Catháin, P. Ó. (2020) · Algorithmica · doi:10.1007/s00453-020-00727-1 · Cited by 12
On the Complexity of Learning from Label Proportions
Fish, B., & Reyzin, L. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/232 · Cited by 12
Polynomial‐time universality and limitations of deep learning
Abbe, E. A., & Sandon, C. (2023) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.22121 · Cited by 33
On the Asymptotics of Solving the LWE Problem Using Coded-BKW With Sieving
Guo, Q., Johansson, T., Martensson, E., & Stankovski, P. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2906233 · Cited by 12
Algorithmic approaches to statistical questions
Papadimitriou, C. H., & Valiant, G. J. (2012) · Cited by 12
Key Recovery for LWE in Polynomial Time.Preprint
Laine, K., & Lauter, K. (2015) · IACR Cryptology ePrint Archive · Cited by 12
Noise-tolerant parity learning with one quantum bit
Park, D. K., Rhee, J.-K. K., & Lee, S. (2018) · Physical Review A · doi:10.1103/physreva.97.032327 · Cited by 12
Characterizing In-Context Learning: When Can Transformers Match Standard Learning Algorithms?
Hawarey, M. (2026) · doi:10.65737/airmcs2026277 · Cited by 11
A Note on Ring-LWE Security in the Case of Fully Homomorphic Encryption
Bonnoron, G., & Fontaine, C. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-71667-1_2 · Cited by 11
Learning DNFs under product distributions via mu--biased quantum Fourier sampling
Kanade, V., Rocchetto, A., & Simone Severini, B. (2019) · Quantum Information and Computation · doi:10.26421/qic19.15-16-1 · Cited by 11
How Do Label Errors Affect Thin Crack Detection by DNNs
Xu, L., Zou, H., & Okatani, T. (2023) · IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) · doi:10.1109/cvprw59228.2023.00464 · Cited by 11
Tree-based HB protocols for privacy-preserving authentication of RFID tags
Halevi, T., Saxena, N., & Halevi, S. (2011) · Journal of Computer Security · doi:10.3233/jcs-2010-0404 · Cited by 11
Attack on the GridCode one-time password
Molloy, I., & Li, N. (2011) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/1966913.1966953 · Cited by 11
The Leakage-Resilience Limit of a Computational Problem Is Equal to Its Unpredictability Entropy
Aggarwal, D., & Maurer, U. M. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25385-0_37 · Cited by 11
Nonnegative Matrix Factorization
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.003 · Cited by 11
Improved Lower Bounds for Learning Intersections of Halfspaces
Klivans, A. R., & Sherstov, A. A. (2006) · Lecture notes in computer science · doi:10.1007/11776420_26 · Cited by 11
Efficient Fully Homomorphic Encryption Scheme.Preprint
Gao, S. (2018) · IACR Cryptology ePrint Archive · Cited by 11
Robust (Deep) Learning Framework Against Dirty Labels and Beyond
Ghiassi, A., Younesian, T., Zhao, Z., Birke, R., Schiavoni, V., & Chen, L. Y. (2019) · IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA) · doi:10.1109/tps-isa48467.2019.00038 · Cited by 10
Statistically Sender-Private OT from LPN and Derandomization
Bitansky, N., & Freizeit, S. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-15982-4_21 · Cited by 10
A Lightweight System-On-Chip Based Cryptographic Core for Low-Cost Devices
Gookyi, D. A. N., & Ryoo, K. (2022) · Sensors · doi:10.3390/s22083004 · Cited by 10
NLHB : A light-weight, provably-secure variant of the HB protocol using simple non-linear functions
Madhavan, M., Thangaraj, A., Viswanathan, K., & Sankarasubramaniam, Y. (2010) · National Conference on Communications · doi:10.1109/ncc.2010.5430152 · Cited by 10
Learning noisy characters, multiplication codes, and cryptographic hardcore predicates
Goldwasser, S., & Akavia, A. (2008) · Cited by 10
Learning using Local Membership QueriesPreprint
Awasthi, P., Feldman, V., & Kanade, V. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1211.0996 · Cited by 10
How Does a Neural Network's Architecture Impact Its Robustness to Noisy Labels?Preprint
Li, J., Zhang, M., Xu, K., Dickerson, J. P., & Ba, J. L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.12896 · Cited by 16
How Practical is Public-Key Encryption Based on LPN and Ring-LPN?Preprint
Damgård, I., & Park, S. (2012) · IACR Cryptology ePrint Archive · Cited by 10
Compact and efficient KEMs over NTRU lattices
Liang, Z., Fang, B., Zheng, J., & Zhao, Y. (2024) · Computer Standards & Interfaces · doi:10.1016/j.csi.2023.103828 · Cited by 9
A Systematic Study of Sparse LWE
Jain, A., Lin, H., & Saha, S. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-68382-4_7 · Cited by 9
An Algorithmic Reduction Theory for Binary Codes: LLL and More
Debris-Alazard, T., Ducas, L., & van Woerden, W. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3143620 · Cited by 9
PRDP: Person Reidentification With Dirty and Poor Data
Xu, F., Ma, B., Chang, H., & Shan, S. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3105970 · Cited by 9
Using Variational Quantum Algorithm to Solve the LWE Problem
Lv, L., Yan, B., Wang, H., Ma, Z., Fei, Y., Meng, X., & Duan, Q. (2022) · Entropy · doi:10.3390/e24101428 · Cited by 10
Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions
Ma, G., & Li, H. (2022) · Quantum · doi:10.22331/q-2022-12-01-866 · Cited by 9
Computationally efficient mutual entity authentication in wireless sensor networks
Li, Z., & Gong, G. (2010) · Ad Hoc Networks · doi:10.1016/j.adhoc.2010.07.007 · Cited by 9
Inter-training: Exploiting unlabeled data in multi-classifier systems
Jiang, Z., Zeng, J., & Zhang, S. (2013) · Knowledge-Based Systems · doi:10.1016/j.knosys.2013.01.028 · Cited by 9
A new birthday-type algorithm for attacking the fresh re-keying countermeasure
Guo, Q., & Johansson, T. (2019) · Information Processing Letters · doi:10.1016/j.ipl.2019.02.005 · Cited by 9
A subexponential-time, polynomial quantum space algorithm for inverting the CM group action
Jao, D., LeGrow, J. T., Leonardi, C., & Ruiz, L. M. (2020) · Journal of Mathematical Cryptology · doi:10.1515/jmc-2015-0057 · Cited by 9
On the Sample Complexity of solving LWE using BKW-Style Algorithms
Guo, Q., Mårtensson, E., & Stankovski, P. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9518190 · Cited by 9
Security evaluation and design elements for a class of randomised encryptions
Mihaljević, M. J., & Oggier, F. (2018) · IET Information Security · doi:10.1049/iet-ifs.2017.0271 · Cited by 9
Scalar Product Lattice Computation for Efficient Privacy-Preserving Systems
Rahulamathavan, Y., Dogan, S., Shi, X., Lu, R., Rajarajan, M., & KONDOZ, A. M. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.3014686 · Cited by 9
Cuong, N. V., Ho, L. S. T., & Dinh, V. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40935-6_19 · Cited by 9
Design and implementation of S-MARKS: A secure middleware for pervasive computing applications
Ahamed, S. I., Li, H., Talukder, N., Monjur, M., & Hasan, C. S. (2009) · Journal of Systems and Software · doi:10.1016/j.jss.2009.03.020 · Cited by 9
Long, P., & Servedio, R. A. (2008) · Cited by 9
Learning Parities with Structured Noise.Preprint
Arora, S., & Ge, R. (2010) · Electronic colloquium on computational complexity · Cited by 9
Computational Limitations in Robust Classification and Win-Win ResultsPreprint
Degwekar, A., Nakkiran, P., & Vaikuntanathan, V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.01086 · Cited by 9
Noisy Labels Can Induce Good Representations.Preprint
Li, J., Zhang, M., Xu, K., Dickerson, J. P., & Ba, J. L. (2020) · arXiv (Cornell University) · Cited by 9
From Local Pseudorandom Generators to Hardness of LearningPreprint
Daniely, A., & Vardi, G. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.08303 · Cited by 9
Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas
Feldman, V., Lee, H. K., Servedio, R. A., Kakade, S., & Ulrike Von Luxburg, A. (2010) · Cited by 8
Reconstruction on Trees and Low-Degree Polynomials
Koehler, F., & Mossel, E. (2022) · neural information processing systems · doi:10.52202/068431-1376 · Cited by 8
New Secret Keys for Enhanced Performance in (T)FHE
Bergerat, L., Chillotti, I., Ligier, D., Orfila, J.-B., Roux-Langlois, A., & Tap, S. (2024) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3658644.3670376 · Cited by 8
SQUiD: ultra-secure storage and analysis of genetic data for the advancement of precision medicine
Blindenbach, J., Kang, J., Hong, S., Karam, C. S., Lehner, T., & Gürsoy, G. (2024) · Genome biology · doi:10.1186/s13059-024-03447-9 · Cited by 8
Solving LWE problem with bounded errors in polynomial time.
Ding, J. (2010) · Cited by 8
On the Security of Non-Linear HB (NLHB) Protocol Against Passive Attack
Reza, M., & Abyaneh, S. (2014) · Cited by 8
Efficient Cryptographic Protocols Based on the Hardness of Learning Parity with Noise
Katz, J. I. (2007) · Springer eBooks · doi:10.1007/978-3-540-77272-9_1 · Cited by 8
A General Characterization of the Statistical Query ComplexityPreprint
Feldman, V. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1608.02198 · Cited by 8
Challenges for Ring-LWE.Preprint
Crockett, E., & Peikert, C. (2016) · IACR Cryptology ePrint Archive · Cited by 8
Memory-Sample Lower Bounds for Learning Parity with NoisePreprint
Garg, S., Kothari, P. K., Liu, P., & Raz, R. (2021) · arXiv (Cornell University) · doi:10.4230/lipics.approx/random.2021.60 · Cited by 8
A two-stage denoising framework for zero-shot learning with noisy labels
Tang, L., Zhao, P., Pan, Z., Duan, X., & Pardalos, P. M. (2023) · Information Sciences · doi:10.1016/j.ins.2023.119852 · Cited by 7
Loki: A Lightweight LWE Method with Rogue Bits for Quantum Security in IoT Devices
Singh, R., Hussain, M. M., Sahay, M., Indu, S., Kaushik, A. K., & Singh, A. K. (2020) · Smart innovation, systems and technologies · doi:10.1007/978-981-15-7062-9_54 · Cited by 7
Evolutionary techniques in lattice sieving algorithms
Laarhoven, T. T. (2019) · TU/e Research Portal · Cited by 7
Chosen-Ciphertext Secure Key Encapsulation Mechanism in the Standard Model
Xu, S., & Li, X. (2021) · IEEE Access · doi:10.1109/access.2021.3051047 · Cited by 7
Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms
Guo, Q., Mårtensson, E., & Stankovski, P. (2022) · Cryptography and Communications · doi:10.1007/s12095-022-00597-0 · Cited by 7
A Close Look to Margin Complexity and Related Parameters
Kallweit, M., & Simon, H. U. (2011) · Conference on Learning Theory · Cited by 7
Lyubashevsky, V. (2005) · Cited by 7
Correlation clustering methodologies and their fundamental results
Pandove, D., Goel, S., & Rani, R. (2017) · Expert Systems · doi:10.1111/exsy.12229 · Cited by 7
Mangoubi, O., & Vishnoi, N. K. (2021) · Mathematics of Operations Research · doi:10.1145/3406325.3451097 · Cited by 10
Physical layer authentication for automotive cyber physical systems based on modified HB protocol
Jadoon, A. K., Li, J., & Wang, L. (2020) · Frontiers of Computer Science · doi:10.1007/s11704-020-0010-4 · Cited by 7
Moitra, A. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316882177.008 · Cited by 7
Attacks on CKK Family of RFID Authentication Protocols
Gołębiewski, Z., Majcher, K., & Zagórski, F. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85209-4_19 · Cited by 7
On the Hardness of Learning Sparse ParitiesPreprint
Bhattacharyya, A., Gadekar, A., Ghoshal, S., & Saket, R. (2015) · arXiv (Cornell University) · doi:10.4230/lipics.esa.2016.11 · Cited by 7
On the list decodability of random linear codes with large error ratesPreprint
Wootters, M. K. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.2261 · Cited by 7
Fully Homomorphic Encryption with k-bit Arithmetic Operations.Preprint
Case, B. M., Gao, S., Hu, G., & Xu, Q. (2019) · IACR Cryptology ePrint Archive · Cited by 7
Predicting Features of Quantum Systems from Very Few MeasurementsPreprint
Huang, H.-Y., & Kueng, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.08909 · Cited by 10
Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices
Zheng, M., Zeng, J., Yang, W., Chang, P.-J., Lu, Q., Yan, B., Zhang, H., Wang, M., Wei, S., & Long, G. (2025) · Communications Physics · doi:10.1038/s42005-025-02126-w · Cited by 11
Improved Lattice Blind Signatures from Recycled Entropy
Jeudy, C., & Sanders, O. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-01855-7_16 · Cited by 6
Stationary Syndrome Decoding for Improved PCGs
Kolesnikov, V., Peceny, S., Raghuraman, S., & Rindal, P. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-01855-7_10 · Cited by 6
Lakum, T., & Rao, B. T. (2019) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2019.0101121 · Cited by 6
On the Security of Homomorphic Encryption Schemes with Restricted Decryption Oracles
Ma, G., & Li, H. (2024) · Journal of Systems Science and Complexity · doi:10.1007/s11424-024-3221-1 · Cited by 6
Feature-Induced Label Distribution for Learning with Noisy Labels
Zhang, M., Xu, N., & Geng, X. (2022) · Pattern Recognition Letters · doi:10.1016/j.patrec.2022.02.011 · Cited by 6
Security estimation of LWE via BKW algorithms
Yu, W., Bi, L., Lu, X., & Wang, K. (2023) · Cybersecurity · doi:10.1186/s42400-023-00158-9 · Cited by 6
Improved Fast Correlation Attacks on the Sosemanuk Stream Cipher
Zhang, B., Liu, R., Gong, X., & Jiao, L. (2023) · IACR Transactions on Symmetric Cryptology · doi:10.46586/tosc.v2023.i4.83-111 · Cited by 6
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
