2023-08-28
Random restrictions of high-rank tensors and polynomial maps
Publication
Publication
Presented at the
12th European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB'23 (August 2023), Prague, Czech Republic
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.5817/CZ.MUNI.EUROCOMB23-033 | |
| Networks | |
| 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 |
|
