LWE versus neural nets It seems like that the construction of the LWE problem: $As + e = b$ resembles how neural nets work: $Ax + b = y$.
In LWE, we are given the problem instance $A$, and the product with errors $b$ and are challenged to produce the secret vector $s$. Is it similar to the problem in ML where we are given the coefficient matrix $A$ and the expected label $y$, can we produce a valid sample $x$?
Also, I'm wondering whether techniques we use in ML such as backpropagation can be applied to LWE as well?
This seems quite unlikely. A recent paper has suggested a Continuous LWE problem. This problem is structurally quite similar to the standard LWE problem --- it has (quantum) worst-case to average-case reductions to hard lattice problems.
In that paper they also show that a
standard problem in ML (learning mixtures of Gaussians) reduces to the continuous LWE problem. This gives you a more concrete ML problem to attack. If you could learn mixtures of Gaussians, you could reduce this to solving continuous LWE, which you could then reduce to solving worst-case lattice problems. If you can solve worst-case lattice problems, then we do not believe LWE is hard anymore.
There have also been some results showing that a broad class of learning algorithms (ones which fit into the &quot;Statistical Query model&quot;) cannot solve certain learning problems. The LPN problem (which you can vaguely think of as &quot;LWE with $q = 2$) has such bounds (see for example this problem). I don't know if specific ML techniques such as backpropagation fit into the SQ model though.