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.

, , , ,
doi.org/10.19086/da.124610
Discrete Analysis
Networks
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