Continuous LWE

Published in In submission, 2020


We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We show the average-case hardness of this problem by a polynomial-time quantum reduction from worst-case lattice problems.

Our hardness result resolves an open problem regarding the computational complexity of density estimation for Gaussian mixtures (Diakonikolas 2016, Moitra 2018). In addition, it addresses an open question by Bubeck et al. (2019), who considered a slight variant of CLWE in the context of robust machine learning.