Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.12390 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912235846107136 |
|---|---|
| author | Yang, Jason |
| author_facet | Yang, Jason |
| contents | We present an $O^*(|\mathbb{F}|^{\min\left\{R,\ \sum_{d\ge 2} n_d\right\} + (R-n_0)(\sum_{d\ne 0} n_d)})$-time algorithm for determining whether the rank of a concise tensor $T\in\mathbb{F}^{n_0\times\dots\times n_{D-1}}$ is $\le R$, assuming $n_0\ge\dots\ge n_{D-1}$ and $R\ge n_0$. For 3-dimensional tensors, we have a second algorithm running in $O^*(|\mathbb{F}|^{n_0+n_2 + (R-n_0+1-r_*)(n_1+n_2)+r_*^2})$ time, where $r_*:=\left\lfloor\frac{R}{n_0}\right\rfloor+1$. Both algorithms use polynomial space and improve on our previous work, which achieved running time $O^*(|\mathbb{F}|^{n_0+(R-n_0)(\sum_d n_d)})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_12390 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster search for tensor decomposition over finite fields Yang, Jason Computational Complexity We present an $O^*(|\mathbb{F}|^{\min\left\{R,\ \sum_{d\ge 2} n_d\right\} + (R-n_0)(\sum_{d\ne 0} n_d)})$-time algorithm for determining whether the rank of a concise tensor $T\in\mathbb{F}^{n_0\times\dots\times n_{D-1}}$ is $\le R$, assuming $n_0\ge\dots\ge n_{D-1}$ and $R\ge n_0$. For 3-dimensional tensors, we have a second algorithm running in $O^*(|\mathbb{F}|^{n_0+n_2 + (R-n_0+1-r_*)(n_1+n_2)+r_*^2})$ time, where $r_*:=\left\lfloor\frac{R}{n_0}\right\rfloor+1$. Both algorithms use polynomial space and improve on our previous work, which achieved running time $O^*(|\mathbb{F}|^{n_0+(R-n_0)(\sum_d n_d)})$. |
| title | Faster search for tensor decomposition over finite fields |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2502.12390 |