论文标题
连续的LWE
Continuous LWE
论文作者
论文摘要
我们介绍了错误的学习（LWE）问题的连续类似物，我们将其命名为Clwe。我们从最差的晶格问题中减少多项式时间量子，向Clwe提供了与LWE相似的硬度保证。另外，我们的结果也可以看作是开放（量子）攻击晶格问题的新途径。我们的工作解决了关于没有可分离性假设的高斯学习混合物的计算复杂性的开放问题（Diakonikolas 2016，Moitra 2018）。作为额外的动机，在强大的机器学习的背景下（Diakonikolas等人〜focs 2017）考虑了CLWE的（一种轻微的变体），其中显示了统计查询（SQ）模型中的硬度。我们的工作解决了有关其计算硬度的开放问题（Bubeck等〜ICML 2019）。
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).
