An improved algorithm for learning sparse parities in the presence of noise
From MaRDI portal
Publication:2034402
DOI10.1016/j.tcs.2021.04.026zbMath1504.68088OpenAlexW3158738660MaRDI QIDQ2034402
Yu Yu, Di Yan, Shuoyao Zhao, Jiang Zhang, Hanlin Liu
Publication date: 22 June 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.04.026
learning theorylearning parity with noisealgorithm analysislearning sparse parity with noisesample amplification
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem
- Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
- Circular and KDM Security for Identity-Based Encryption
- Low Noise LPN: KDM Secure Public Key Encryption and Sample Amplification
- On Noise-Tolerant Learning of Sparse Parities and Related Problems
- (Almost) Optimal Constructions of UOWHFs from 1-to-1, Regular One-Way Functions and Beyond
- Parallel and Concurrent Security of the HB and HB + Protocols
- Cryptography with Constant Input Locality
- On the inherent intractability of certain coding problems (Corresp.)
- A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511
- Bi-Deniable Public-Key Encryption
- Smaller Decoding Exponents: Ball-Collision Decoding
- Efficient noise-tolerant learning from statistical queries
- Simple Chosen-Ciphertext Security from Low-Noise LPN
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN
- Noise-tolerant learning, the parity problem, and the statistical query model
This page was built for publication: An improved algorithm for learning sparse parities in the presence of noise
