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 $\hat{I}˜(k\log n/\mathsf{poly}(\log k,\log q,\log \log n))$ with a u…