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 301–400 of 602
On the Security of Non-Linear HB (NLHB) Protocol against Passive Attack
Abyaneh, M. R. S. (2010) · IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC) · doi:10.1109/euc.2010.86 · Cited by 6
Bischof, C. H., Buchmann, J. A., Dagdelen, Ö., Fitzpatrick, R., Göpfert, F., & Mariano, A. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-21356-9_14 · Cited by 6
Post-quantum Provably-Secure Authentication and MAC from Mersenne Primes
Ferradi, H., & Xagawa, K. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-40186-3_20 · Cited by 6
Quantum solvability of noisy linear problems by divide-and-conquer strategy
Song, W., Lim, Y., Jeong, K., Ji, Y.-S., Lee, J., Kim, J., Kim, M. S., & Bang, J. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac51b0 · Cited by 6
Chen, Y.-A., Gao, X.-S., & Yuan, C.-M. (2025) · Journal of Systems Science and Complexity · doi:10.1007/s11424-024-4545-6 · Cited by 6
Hardness of learning problems over Burnside groups of exponent 3
Fazio, N., Iga, K., Nicolosi, A. R., Perret, L., & Skeith, W. E. (2013) · Designs Codes and Cryptography · doi:10.1007/s10623-013-9892-6 · Cited by 6
Practical Attacks on HB and HB+ Protocols
Gołębiewski, Z., Majcher, K., Zagórski, F., & Zawada, M. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-21040-2_17 · Cited by 6
Evolution is exponentially more powerful with frequency-dependent selectionPreprint
Kaznatcheev, A. (2020) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2020.05.03.075069 · Cited by 6
A Second-order Equilibrium in Nonconvex-Nonconcave Min-max Optimization: Existence and Algorithm.Preprint
Mangoubi, O., & Vishnoi, N. K. (2020) · arXiv (Cornell University) · Cited by 6
On the Hardness of Average-Case k-SUMPreprint
Brakerski, Z., Stephens-Davidowitz, N., & Vaikuntanathan, V. (2020) · arXiv (Cornell University) · doi:10.4230/lipics.approx/random.2021.29 · Cited by 6
REDsec: Running Encrypted DNNs in Seconds.Preprint
Folkerts, L. W., Gouert, C., & Tsoutsos, N. G. (2021) · IACR Cryptology ePrint Archive · Cited by 6
MILD: Modeling the Instance Learning Dynamics for Learning with Noisy Labels
Hu, C., Yan, S., Gao, Z., & He, X. (2023) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2023/92 · Cited by 5
A Unified Open Adapter for Open-World Noisy Label Learning: Data-Centric and Learning-Based Insights
Zong, C.-C., Yang, P., Xie, M.-K., & Huang, S.-J. (2025) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2025.3550899 · Cited by 5
On Algebraic Homomorphic Encryption and Its Applications to Doubly-Efficient PIR
Okada, H., Player, R., Pohmann, S., & Weinert, C. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-91095-1_2 · Cited by 5
Quantum learning Boolean linear functions w.r.t. product distributions
Caro, M. C. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02661-1 · Cited by 5
On the universality of deep learning
Abbe, E. A., & Sandon, C. (2020) · neural information processing systems · Cited by 5
Fiat-Shamir with Aborts: From Identification Schemes to Linkable Ring Signatures
Das, D. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-66626-2_9 · Cited by 5
Data fusing and joint training for learning with noisy labels
Wei, Y., Mei, X., Liu, X., & Xu, P. (2022) · Frontiers of Computer Science · doi:10.1007/s11704-021-1208-9 · Cited by 5
Cooperation for secure wireless communications with resource-bounded eavesdroppers
Kolokotronis, N., Fytrakis, K., Katsiotis, A., & Kalouptsidis, N. (2014) · IEEE Globecom Workshops (GC Wkshps) · doi:10.1109/glocomw.2014.7063626 · Cited by 5
Practical Analysis of Key Recovery Attack Against Search-LWE Problem
Kudo, M., Yamaguchi, J., Guo, Y., & Yasuda, M. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-44524-3_10 · Cited by 5
The Implications of Local Correlation on Learning Some Deep Functions
Malach, E., & Shalev‐Shwartz, S. (2020) · neural information processing systems · Cited by 5
A Faster Subquadratic Algorithm for Finding Outlier Correlations
Karppa, M., Kaski, P., & Kohonen, J. (2018) · ACM Transactions on Algorithms · doi:10.1145/3174804 · Cited by 5
The Approximate k-List Problem
Both, L., & May, A. (2017) · IACR Transactions on Symmetric Cryptology · doi:10.46586/tosc.v2017.i1.380-397 · Cited by 5
Prati, R. C. (2006) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/t.55.2006.tde-01092006-155445 · Cited by 5
Complexity Theoretic Limitations on Learning HalfspacesPreprint
Daniely, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1505.05800 · Cited by 6
NLHB : A Non-Linear Hopper Blum ProtocolPreprint
Madhavan, M., Thangaraj, A., Sankarasubramaniam, Y., & Viswanathan, K. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1001.2140 · Cited by 5
From average case complexity to improper learning complexityPreprint
Daniely, A., Linial, N., & Shalev‐Shwartz, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.2272 · Cited by 7
ID3 Learns Juntas for Smoothed Product DistributionsPreprint
Blanc, G., Lange, J., & Tan, L.-Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.08654 · Cited by 5
A joint training framework for learning with noisy labels
Wei, Q., Sun, H., Ma, Y., & Yin, Y. (2023) · Scientia Sinica Informationis · doi:10.1360/ssi-2022-0395 · Cited by 4
Combating Noisy Labels by Alleviating the Memorization of DNNs to Noisy Labels
Yuan, S. W., Li, X., Miao, Y., Zhang, H., Liu, X., & Deng, R. H. (2024) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2024.3521722 · Cited by 5
Lin, C., Yang, K., Xu, T., Liang, L., Wang, Y., Chen, Z., Wang, R., Gao, M., & Li, M. (2025) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3725843.3756025 · Cited by 5
Oblivious network intrusion detection systems
Sayed, M. A., & Taha, M. M. I. (2023) · Scientific Reports · doi:10.1038/s41598-023-48475-w · Cited by 4
From learning with errors (LWE) problem to CLWE problem
Zhao, J. (2023) · Theoretical and Natural Science · doi:10.54254/2753-8818/26/20241119 · Cited by 4
k-SUM in the Sparse Regime: Complexity and Applications
Agrawal, S., Saha, S., Schwartzbach, N. I., Vanukuri, A., & Vasudevan, P. N. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-68379-4_10 · Cited by 4
Two Attacks against the F f RFID Protocol
Billet, O., & Elkhiyaoui, K. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10628-6_21 · Cited by 4
Kolokotronis, N., Katsiotis, A., & Kalouptsidis, N. (2014) · ACM Conference on Security and Privacy in Wireless and Mobile Networks (WiSec) · doi:10.1145/2627393.2627413 · Cited by 4
Homomorphic Evaluation Requires Depth
Bogdanov, A., & Lee, C. H. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-49096-9_15 · Cited by 4
Light-hHB: A New Version of hHB with Improved Session Key Exchange
Ka, A. K. (2016) · Cited by 4
Better Key Sizes (and Attacks) for LWE-Based Encryption.
Lindner, R., & Peikert, C. (2010) · Cited by 4
Non-interactive Secure Computation of Inner-Product from LPN and LWE
Couteau, G., & Zarezadeh, M. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-22963-3_16 · Cited by 4
On the Learnability of Monotone Functions
Lee, H. K. (2009) · doi:10.7916/d8w66sm1 · Cited by 4
Simpler CCA Secure PKE from LPN Problem Without Double-Trapdoor
Cheng, H., Li, X., Qian, H., & Yan, D. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-01950-1_46 · Cited by 4
BKW Meets Fourier New Algorithms for LPN with Sparse Parities
Dachman-Soled, D., Gong, H., Kippen, H., & Shahverdi, A. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-90453-1_23 · Cited by 4
On Public Key Encryption from Noisy Codewords
Ben‐Sasson, E., Bentov, I., Damgård, I., Ishai, Y., & Ron‐Zewi, N. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49387-8_16 · Cited by 4
Active EM to reduce noise in activity recognition
Shen, J., & Dietterich, T. G. (2007) · ACM International Conference on Intelligent User Interfaces (IUI) · doi:10.1145/1216295.1216323 · Cited by 4
Stange, K. E. (2021) · SIAM Journal on Applied Algebra and Geometry · doi:10.1137/19m1280442 · Cited by 4
Homophonic Coding Design for Communication Systems Employing the Encoding-Encryption ParadigmPreprint
Mihaljević, M. J., Oggier, F., & Imai, H. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.5895 · Cited by 4
Quantum algorithms for highly non-linear Boolean functionsPreprint
Roetteler, M. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0811.3208 · Cited by 4
MetaInfoNet: Learning Task-Guided Information for Sample ReweightingPreprint
Wei, H., Feng, L., Wang, R., & An, B. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.05273 · Cited by 4
One Network Fits All? Modular versus Monolithic Task Formulations in Neural NetworksPreprint
Agarwala, A., Das, A., Juba, B., Panigrahy, R., Sharan, V., Wang, X. Y., & Zhang, Q. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.15261 · Cited by 4
Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart NoisePreprint
Diakonikolas, I., & Kane, D. M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.09720 · Cited by 18
Compact and Efficient Kems Over Ntru LatticesPreprint
Liang, Z., Fang, B., Zheng, J., & Zhao, Y. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4605000 · Cited by 4
DAWN: Smaller and Faster NTRU Encryption via Double Encoding
Liu, Y., Zhang, Y., Lu, X., Cheng, Y., & Yin, Y. (2025) · Lecture notes in computer science · doi:10.1007/978-981-95-5099-9_13 · Cited by 3
New Results for Random Walk Learning.
Jackson, J. C., & Wimmer, K. (2009) · Cited by 3
Chang, Y., Tai, W., & Chen, C. (2013) · Informatica · doi:10.15388/informatica.2013.381 · Cited by 3
Teixidó, I., Sebé, F., Conde, J., & Solsona, F. (2014) · Parallel Computing · doi:10.1016/j.parco.2014.04.002 · Cited by 3
Quantum-classical reinforcement learning for decoding noisy classical parity information
Park, D. K., Park, J., & Rhee, J.-K. K. (2020) · Quantum Machine Intelligence · doi:10.1007/s42484-020-00019-5 · Cited by 4
An Improved BKW Algorithm For LWE With Binary Uniform Errors
Qian, X., Liu, J., Gu, C., & Zheng, Y. (2020) · International Conference on Computer and Communication Systems (ICCCS) · doi:10.1109/icccs49078.2020.9118492 · Cited by 3
Proceedings of the Second International Forum on Financial Mathematics and Financial Technology
Zheng, Z. (2023) · Financial Mathematics and Fintech · doi:10.1007/978-981-99-2366-3 · Cited by 3
Symmetric Perceptrons, Number Partitioning and Lattices
Vafa, N., & Vaikuntanathan, V. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718263 · Cited by 3
On the LWE Cryptosystem with More General Disturbance
Zheng, Z., & Tian, K. (2022) · Journal of Information Security · doi:10.4236/jis.2022.133008 · Cited by 3
Song, W., Lim, Y., Jeong, K., Lee, J., Park, J. J., Kim, M. S., & Bang, J. (2022) · New Journal of Physics · doi:10.1088/1367-2630/ac94ef · Cited by 3
Algebraic solvers for certain lattice-related problems
Ding, J. (2011) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2011.6089489 · Cited by 3
Secretly Pruned Convolutional Codes: Security Analysis and Performance Results
Kolokotronis, N., Katsiotis, A., & Kalouptsidis, N. (2016) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2016.2537262 · Cited by 3
Guo, Q., & Johansson, T. (2016) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2016.7541520 · Cited by 3
An efficient distributed protein disorder prediction with pasted samples
Smith, D., Yenduri, S., Iqbal, S., & Krishna, P. V. (2017) · Computers & Electrical Engineering · doi:10.1016/j.compeleceng.2017.08.002 · Cited by 3
Téllez, C., Pereira, D. A. B., & Borges, F. (2019) · IEEE International Workshop on Metrology for Industry 4.0 & IoT (MetroInd4.0&IoT) · doi:10.1109/metroi4.2019.8792913 · Cited by 3
Federated Learning is Better with Non-Homomorphic Encryption
Burlachenko, K., Alrowithi, A., Albalawi, F., & Richtárik, P. (2023) · doi:10.1145/3630048.3630182 · Cited by 5
Lower bounds in communication complexity and learning theory via analytic methods
Klivans, A. R., & Sherstov, A. A. (2009) · Cited by 3
Lightweight Privacy for Ubiquitous Devices
Otsuka, A., Shigetomi, R., & Imai, H. (2006) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.2006.384883 · Cited by 3
Approximation Algorithms and New Models for Clustering and Learning
Awasthi, P. (2013) · doi:10.1184/r1/6714833 · Cited by 3
Spectral Norm in Learning Theory: Some Selected Topics
Simon, H. U. (2006) · Lecture notes in computer science · doi:10.1007/11894841_4 · Cited by 3
On learning k-parities with and without noisePreprint
Bhattacharyya, A., Gadekar, A., & Rajgopal, N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.05375 · Cited by 3
Physical-layer security: practical aspects of channel coding and cryptography
Harrison, W. K. (2012) · SMARTech Repository (Georgia Institute of Technology) · Cited by 3
Learning Boolean Circuits with Neural NetworksPreprint
Malach, E., & Shalev‐Shwartz, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.11923 · Cited by 3
Securing Systems with Scarce Entropy: LWE-Based Lossless Computational Fuzzy Extractor for the IoT.Preprint
Huth, C., Becker, D., Guajardo, J., Duplys, P., & Güneysu, T. E. (2016) · IACR Cryptology ePrint Archive · Cited by 3
CCA1-secure somewhat homomorphic encryption
Morais, E. (2016) · doi:10.47749/t/unicamp.2016.977097 · Cited by 3
Security and privacy in RFID systems
Elkhiyaoui, K. (2012) · doi:10.70675/2c9d0090z0335z4568z8874z9e2c58f31711 · Cited by 3
A journey towards practical fully homomorphic encryption
Bonnoron, G. (2018) · doi:10.70675/56bcc9fcz1508z4cc9zac79ze1fe4f9403a5 · Cited by 3
Schuster, T., Kalyan, A., Polozov, O., & Kalai, A. T. (2021) · arXiv · doi:10.48550/arxiv.2106.05784 · Cited by 2
Self-citationAnalysis of learning with errors problems with variational quantum algorithms
Zeng, J., Zheng, M., Li, H., Wei, S., & Long, G. (2025) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/add959 · Cited by 3
Zelenetsky, A. S., & Klyucharev, P. G. (2025) · Journal of Computer Virology and Hacking Techniques · doi:10.1007/s11416-025-00576-y · Cited by 2
The HHE Land: Exploring the Landscape of Hybrid Homomorphic Encryption
Abdinasibfar, H., Nuoskala, C., & Michalas, A. (2026) · ACM Computing Surveys · doi:10.1145/3807507 · Cited by 2
KDM-Secure Public-Key Encryption from Constant-Noise LPN
Han, S., & Liu, S. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-60055-0_3 · Cited by 2
Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR
Dinur, I., Keller, N., & Klein, O. (2024) · Journal of the ACM · doi:10.1145/3653014 · Cited by 2
Instantiating the Hash-Then-Evaluate Paradigm: Strengthening PRFs, PCFs, and OPRFs
Brzuska, C., Couteau, G., Egger, C., Karanko, P., & Meyer, P. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-71073-5_5 · Cited by 2
Quantum-Resistant Encryption For Secure End-to-End Communication
Sameer, K., Kishor, J. N., Singh, J., Dilip, S., & Kumar, S. A. (2024) · ITU Kaleidoscope Academic Conference (ITU K) · doi:10.23919/ituk62727.2024.10772922 · Cited by 2
Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Bangachev, K., Bresler, G., Tiegel, S., & Vaikuntanathan, V. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718284 · Cited by 2
Wagner’s Algorithm Provably Runs in Subexponential Time for $$\textrm{SIS}^\infty $$
Ducas, L., Engelberts, L., & Loyer, J. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-01855-7_12 · Cited by 2
Fast Algorithm to solve a family of SIS problem with l infty norm.
Ding, J. (2010) · Cited by 2
Identifying the Training Stop Point with Noisy Labeled Data
Kamabattula, S., Devarajan, V., Namazi, B., & Sankaranarayanan, G. (2020) · International Conference on Computational Science and Computational Intelligence (CSCI) · doi:10.1109/csci51800.2020.00084 · Cited by 2
An Improved BKW Algorithm for Solving LWE with Small Secrets
Wei, Y. J., Bi, L., Wang, K., & Lu, X. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-49187-0_29 · Cited by 2
Learning with Noisy Labels: A Novel Meta Label Corrector without Clean Validation Data
Jiang, K. Y., Cao, B., Liu, Y., & Fan, J. (2024) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn60899.2024.10651351 · Cited by 2
Post-quantum cryptography: lattice identification schemes
Silva, R., Cayrel, P.-L., & Buchmann, J. A. (2011) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.2011.5311 · Cited by 2
Known plaintext attack on the binary symmetric wiretap channel
Vaidyanathaswami, R., & Thangaraj, A. (2011) · IEEE Globecom Workshops (GC Wkshps) · doi:10.1109/glocomw.2011.6162588 · Cited by 2
A low complexity authentication protocol based on pseudorandomness, randomness and homophonic coding
Mihaljević, M. J., Watanabe, H., & Imai, H. (2010) · International Symposium on Information Theory and its Applications · doi:10.1109/isita.2010.5649666 · Cited by 2
RFID System Security Using Identity-Based Cryptography
Chen, Y., Chen, Z., & Xu, L. (2010) · International Symposium on Intelligent Information Technology and Security Informatics · doi:10.1109/iitsi.2010.52 · Cited by 2
REAL UNDERSTANDING OF LPN-PROBLEM-BASED LIGHTWEIGHT AUTHENTICATION PROTOCOLS
Chang, Y. (2010) · Information Technology And Control · doi:10.5755/j01.itc.39.3.12304 · Cited by 2
Picazo‐Sanchez, P., Ortiz‐Martin, L., Lopez, P. P., & Hernandez-Castro, J. C. (2012) · IGI Global eBooks · doi:10.4018/978-1-4666-1990-6.ch002 · Cited by 2
Spectral Norm in Learning Theory: Some Selected Topics
Simon, H. U. (2006) · Lecture notes in computer science · doi:10.1007/11893318_5 · Cited by 2
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
