Continuous LWE

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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).

Original languageEnglish (US)
Title of host publicationSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
EditorsSamir Khuller, Virginia Vassilevska Williams
PublisherAssociation for Computing Machinery
Pages694-707
Number of pages14
ISBN (Electronic)9781450380539
DOIs
StatePublished - Jun 15 2021
Event53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy
Duration: Jun 21 2021Jun 25 2021

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Country/TerritoryItaly
CityVirtual, Online
Period6/21/216/25/21

Keywords

  • computational learning theory
  • cryptography
  • lattices
  • Learning with Errors
  • mixture of Gaussians
  • quantum computing

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Continuous LWE'. Together they form a unique fingerprint.

Cite this