ECCC-Report TR20-080https://eccc.weizmann.ac.il/report/2020/080Comments and Revisions published for TR20-080en-usWed, 11 Nov 2020 21:21:31 +0200
Revision 1
| Continuous LWE |
Joan Bruna,
Oded Regev,
Min Jae Song,
Yi Tang
https://eccc.weizmann.ac.il/report/2020/080#revision1We 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).Wed, 11 Nov 2020 21:21:31 +0200https://eccc.weizmann.ac.il/report/2020/080#revision1
Paper TR20-080
| Continuous LWE |
Joan Bruna,
Oded Regev,
Min Jae Song,
Yi Tang
https://eccc.weizmann.ac.il/report/2020/080We 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).Thu, 21 May 2020 17:39:43 +0300https://eccc.weizmann.ac.il/report/2020/080