Random restrictions of high-rank tensors and polynomial maps

EUROCOMB’23

Abstract
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.

Pages:
238–244
References

Jop Briët, Harry Buhrman, Davi Castro-Silva, and Niels M. P. Neumann, Noisy decoding by shallow circuits with parities: classical and quantum, 2023.

Jop Briët and Davi Castro-Silva, Random restrictions of high-rank tensors and polynomial maps, 2022.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-033

Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach, Progression-free sets in Z n 4 are exponentially small, Ann. of Math. (2) 185 (2017), no. 1, 331-337. MR 3583357
https://doi.org/10.4007/annals.2017.185.1.7

Jordan S. Ellenberg and Dion Gijswijt, On large subsets of F nq with no three-term arithmetic progression, Ann. of Math. (2) 185 (2017), no. 1, 339-343. MR 3583358
https://doi.org/10.4007/annals.2017.185.1.8

Ehud Friedgut, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica 18 (1998), no. 1, 27-35. MR 1645642
https://doi.org/10.1007/PL00009809

W. T. Gowers and J. Wolf, Linear forms and higher-degree uniformity for functions on F np , Geom. Funct. Anal. 21 (2011), no. 1, 36-69. MR 2773103
https://doi.org/10.1007/s00039-010-0106-3

Ben Green and Terence Tao, The distribution of polynomials over finite fields, with applications to the Gowers norms, Contrib. Discrete Math. 4 (2009), no. 2, 1-36. MR 2592422

Torben Hagerup and Christine Rüb, A guided tour of Chernoff bounds, Information Processing Letters 33 (1990), no. 6, 305-308.
https://doi.org/10.1016/0020-0190(90)90214-I

Thomas Karam, High-rank subtensors of high-rank tensors, 2022, arXiv:2207.08030.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-089

Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam, Geometric rank of tensors and subrank of matrix multiplication, 35th Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 169, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020, pp. Art. No. 35, 21.

Eric Naslund, Exponential bounds for the Erdős-Ginzburg-Ziv constant, J. Combin. Theory Ser. A 174 (2020), 105185, 19.
https://doi.org/10.1016/j.jcta.2019.105185

Eric Naslund, The partition rank of a tensor and k-right corners in F nq , J. Combin. Theory Ser. A 174 (2020), 105190, 25. MR 4078997
https://doi.org/10.1016/j.jcta.2019.105190

Wolfgang M. Schmidt, The density of integer points on homogeneous varieties, Acta Math. 154 (1985), no. 3-4, 243-296. MR 781588
https://doi.org/10.1007/BF02392473

Michel Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Inst. Hautes Études Sci. Publ. Math. (1995), no. 81, 73-205. MR 1361756
https://doi.org/10.1007/BF02699376

Terence Tao, https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/, 2016.

Terence Tao and Will Sawin, https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/, 2016.

Terence Tao and Tamar Ziegler, The inverse conjecture for the Gowers norm over finite fields in low characteristic, Ann. Comb. 16 (2012), no. 1, 121-188. MR 2948765
https://doi.org/10.1007/s00026-011-0124-3

Metrics

0

Views

0

PDF views