Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations

We present a polynomial-time reduction from solving noisy linear equations over ℤ/ ℤ in dimension Θ( log /poly(log , log , log log )) with a uniformly random coefficient matrix to noisy linear equations over ℤ/ ℤ in dimension where each row of the coefficient matrix has uniformly random support of size . is allows us to deduce the hardness of sparse problems from their dense counterparts. In particular, we derive hardness results in the following canonical se ings: 1. Assuming the -dimensional (dense) learning with errors (LWE) problem over a polynomial-size field takes time 2 Ω( ) , -sparse LWE in dimension takes time 2. Assuming the -dimensional (dense) learning parity with noise (LPN) problem over 2 takes time 2 Ω( / log ) , -sparse LPN in dimension takes time Ω( /(log ⋅(log +log log ) 2 )) . ese running time lower bounds are nearly tight as both sparse problems can be solved in time ( ) , given sufficiently many samples. Our reduction allows us to derive several consequences in cryptography and the computational complexity of statistical problems. In addition, as a new application, we give a reduction from -sparse LWE to noisy tensor completion. Concretely, composing the two reductions implies that order-rank-2 -1 noisy tensor completion in ℝ ⊗ takes time Ω( / log ⋅(log +log log )) , assuming the exponential hardness of standard worst-case la ice problems. Our reduction is (nearly) lossless and extremely versatile: it preserves the number of samples up to a 1-(1) multiplicative factor with high probability and it preserves the noise distribution. In particular, it also applies to the learning with rounding problem. e same reduction works for a wide range of ring sizes from = 2 to that is super-polynomial in the initial dimension and for varying support sizes between samples. Finally, our reduction is compatible with decision (testing), search, and strong refutation and, hence, reduces hardness in the sparse se ing to that of the standard, dense, se ing for all three tasks.