mlsanityData to 7 Oct 2026

Continuous LWE

arXiv 2005.09595 ↗First posted 19 May 2020cs.CC cs.DS cs.LGcited by 37

Not on the map. Why?

Abstract (arXiv)

We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues of (quantum) attacks on lattice problems. Our work resolves an open problem regarding the computational complexity of learning mixtures of Gaussians without separability assumptions (Diakonikolas 2016, Moitra 2018). As an additional motivation, (a slight variant of) CLWE was considered in the context of robust machine learning (Diakonikolas et al.~FOCS 2017), where hardness in the statistical query (SQ) model was shown; our work addresses the open question regarding its computational hardness (Bubeck et al.~ICML 2019).

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 May 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 8; 2023: 5; 2024: 13; 2025: 3; 2026: 4.

37 papers.

Sort:

By area:

  1. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 440
  2. 2023Learning Mixtures of Gaussians Using the DDPM Objectivecited by 56
  3. 2022Planting Undetectable Backdoors in Machine Learning Modelscited by 55
  4. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  5. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  6. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  7. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  8. 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
  9. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  10. 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
  11. 2021Non-Gaussian Component Analysis via Lattice Basis Reductioncited by 14
  12. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
25 more
  1. 2021The Fine-Grained Hardness of Sparse Linear Regressioncited by 12
  2. 2022Learning (Very) Simple Generative Models Is Hardcited by 9
  3. 2024Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamicscited by 8
  4. 2024Improved Hardness Results for Learning Intersections of Halfspacescited by 6
  5. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  6. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 5
  7. 2024Computational-Statistical Gaps for Improper Learning in Sparse Linear Regressioncited by 4
  8. 2024Efficient Certificates of Anti-Concentration Beyond Gaussianscited by 4
  9. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  10. 2023SQ Lower Bounds for Random Sparse Planted Vector Problemcited by 3
  11. 2024Cryptographic Hardness of Score Estimationcited by 3
  12. 2024Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Modelscited by 2
  13. 2022Understanding Impacts of Task Similarity on Backdoor Attack and Detectioncited by 1
  14. 2024Sparse Linear Regression and Lattice Problemscited by 1
  15. 2024On the Hardness of Learning One Hidden Layer Neural Networkscited by 1
  16. 2024CLUE-MARK: Watermarking Diffusion Models using CLWEcited by 1
  17. 2026Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transformscited by 1
  18. 2026Statistically Undetectable Backdoors in Deep Neural Networkscited by 1
  19. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  20. 2023Polynomial Bounds for Learning Noisy Optical Physical Unclonable Functions and Connections to Learning With Errorscited by 0
  21. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  22. 2025A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomialscited by 0
  23. 2025On Learning Parallel Pancakes with Mostly Uniform Weightscited by 0
  24. 2026Low-Degree Method Fails to Predict Robust Subspace Recoverycited by 0
  25. 2026Implementing a White-Box Undetectable Backdoor for Random Fourier Featurescited by 0