2024-11-05
Random restrictions of high-rank tensors and polynomial maps
Publication
Publication
Discrete Analysis p. 1- 23
Motivated by a problem in computational complexity, we consider the behavior of rank functions for tensors and polynomial maps under random coordinate restrictions. We show that, for a broad class of rank functions called natural rank functions, random coordinate restriction to a dense set will typically reduce the rank by at most a constant factor.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.19086/da.124610 | |
| Discrete Analysis | |
| Networks | |
| Organisation | Algorithms and Complexity |
|
Briët, J., & Castro-Silva, D. (2024). Random restrictions of high-rank tensors and polynomial maps. Discrete Analysis, 1–23. doi:10.19086/da.124610 |
|
