Continuous LWE
Continuous LWE
复制标题
连续LWE
DOI：
10.1145/3406325.3451000
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tang, Yi
中科院分区：
文献类型：
--
作者：
Bruna, Joan;Regev, Oded;Song, Min Jae;Tang, Yi
我们介绍了一个连续的模拟学习错误（LWE）的问题，我们命名为CLWE。我们给出了一个多项式时间量子减少从最坏情况下的晶格问题CLWE，CLWE享有类似的硬度保证LWE。或者，我们的结果也可以被看作是打开新的途径（量子）攻击晶格问题。我们的工作解决了一个关于在没有可分性假设的情况下学习高斯混合物的计算复杂性的公开问题（Diakonikolas 2016，Moitra 2018）。作为额外的动机，在鲁棒机器学习的背景下考虑了CLWE（的轻微变体）（Diakonikolas et al. FOCS 2017），其中显示了统计查询（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).
登录
查看更多内容
列表可解码线性回归
DOI：
--
发表时间：
2019
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Karmalkar, Sushrut;Klivans, Adam;Kothari, Pravesh
通讯作者：
Kothari, Pravesh
DOI：
10.1145/3188745.3188758
发表时间：
2017-11
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
通讯作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
影响因子：
1
作者：
R. Rubinfeld;R. Servedio
通讯作者：
R. Servedio
DOI：
--
发表时间：
2018-05
期刊：
ArXiv
影响因子：
--
作者：
Sébastien Bubeck;Eric Price;Ilya P. Razenshteyn
通讯作者：
Sébastien Bubeck;Eric Price;Ilya P. Razenshteyn
DOI：
10.1109/focs.2008.48
发表时间：
2008-04
期刊：
2008 49th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Charles Brubaker;S. Vempala
通讯作者：
Charles Brubaker;S. Vempala