Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912126646353920 |
|---|---|
| author | Bangachev, Kiril Bresler, Guy Tiegel, Stefan Vaikuntanathan, Vinod |
| author_facet | Bangachev, Kiril Bresler, Guy Tiegel, Stefan Vaikuntanathan, Vinod |
| contents | We present a polynomial-time reduction from solving noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $Θ(k\log n/\mathsf{poly}(\log k,\log q,\log\log n))$ with a uniformly random coefficient matrix to noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $n$ where each row of the coefficient matrix has uniformly random support of size $k$. This allows us to deduce the hardness of sparse problems from their dense counterparts. In particular, we derive hardness results in the following canonical settings. 1) Assuming the $\ell$-dimensional (dense) LWE over a polynomial-size field takes time $2^{Ω(\ell)}$, $k$-sparse LWE in dimension $n$ takes time $n^{Ω({k}/{(\log k \cdot (\log k + \log \log n))})}.$ 2) Assuming the $\ell$-dimensional (dense) LPN over $\mathbb{F}_2$ takes time $2^{Ω(\ell/\log \ell)}$, $k$-sparse LPN in dimension $n$ takes time $n^{Ω(k/(\log k \cdot (\log k + \log \log n)^2))}~.$ These running time lower bounds are nearly tight as both sparse problems can be solved in time $n^{O(k)},$ given sufficiently many samples. We further give a reduction from $k$-sparse LWE to noisy tensor completion. Concretely, composing the two reductions implies that order-$k$ rank-$2^{k-1}$ noisy tensor completion in $\mathbb{R}^{n^{\otimes k}}$ takes time $n^{Ω(k/ \log k \cdot (\log k + \log \log n))}$, assuming the exponential hardness of standard worst-case lattice problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_12512 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations Bangachev, Kiril Bresler, Guy Tiegel, Stefan Vaikuntanathan, Vinod Computational Complexity Cryptography and Security Discrete Mathematics Statistics Theory We present a polynomial-time reduction from solving noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $Θ(k\log n/\mathsf{poly}(\log k,\log q,\log\log n))$ with a uniformly random coefficient matrix to noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $n$ where each row of the coefficient matrix has uniformly random support of size $k$. This allows us to deduce the hardness of sparse problems from their dense counterparts. In particular, we derive hardness results in the following canonical settings. 1) Assuming the $\ell$-dimensional (dense) LWE over a polynomial-size field takes time $2^{Ω(\ell)}$, $k$-sparse LWE in dimension $n$ takes time $n^{Ω({k}/{(\log k \cdot (\log k + \log \log n))})}.$ 2) Assuming the $\ell$-dimensional (dense) LPN over $\mathbb{F}_2$ takes time $2^{Ω(\ell/\log \ell)}$, $k$-sparse LPN in dimension $n$ takes time $n^{Ω(k/(\log k \cdot (\log k + \log \log n)^2))}~.$ These running time lower bounds are nearly tight as both sparse problems can be solved in time $n^{O(k)},$ given sufficiently many samples. We further give a reduction from $k$-sparse LWE to noisy tensor completion. Concretely, composing the two reductions implies that order-$k$ rank-$2^{k-1}$ noisy tensor completion in $\mathbb{R}^{n^{\otimes k}}$ takes time $n^{Ω(k/ \log k \cdot (\log k + \log \log n))}$, assuming the exponential hardness of standard worst-case lattice problems. |
| title | Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations |
| topic | Computational Complexity Cryptography and Security Discrete Mathematics Statistics Theory |
| url | https://arxiv.org/abs/2411.12512 |