Random restrictions of high-rank tensors and polynomial maps
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.
|12th European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB'23|
|Organisation||Algorithms and Complexity|
Briët, J, & Castro-Silva, D. (2023). Random restrictions of high-rank tensors and polynomial maps. In Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB'23 (pp. 238–244). doi:10.5817/CZ.MUNI.EUROCOMB23-033