Continuous LWE
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).
Code (0)
등록된 구현이 없습니다.
Tasks
Open-Ended Question AnsweringSimilar Papers 제목 키워드 기반
Reducing Discontinuous to Continuous Parsing with Pointer Network Reordering
Discontinuous constituent parsers have always lagged behind continuous approaches in terms of accuracy and speed, as the presence of constituents with discontinuous yield introduces extra complexity to the task. However,…
SentenceContinuous Submodular Function Maximization
Continuous submodular functions are a category of generally non-convex/non-concave functions with a wide spectrum of applications. The celebrated property of this class of functions - continuous submodularity - enables b…
Discrete-Continuous Smoothing and Mapping
We describe a general approach for maximum a posteriori (MAP) inference in a class of discrete-continuous factor graphs commonly encountered in robotics applications. While there are openly available tools providing flex…
Point Cloud RegistrationAsset Trading in Continuous Time: A Cautionary Tale
The continuous time model of dynamic asset trading is the central model of modern finance. Because trading cannot in fact take place at every moment of time, it would seem desirable to show that the continuous time model…
Faster Policy Learning with Continuous-Time Gradients
We study the estimation of policy gradients for continuous-time systems with known dynamics. By reframing policy learning in continuous-time, we show that it is possible construct a more efficient and accurate gradient e…