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 |