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

Kiril Bangachev, Guy Bresler, Stefan Tiegel +1

We present a polynomial-time reduction from solving noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $\Theta (k\log n/\mathsf{poly}(\log k,\log q,\log \log n))$ with a un…