Geodesic
Structure vs. Randomness for Bilinear Maps
Discrete analysis (2022) Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

We prove that the slice rank of a 3-tensor (a combinatorial notion introduced by Tao in the context of the cap-set problem), the analytic rank (a Fourier-theoretic notion introduced by Gowers and Wolf), and the geometric rank (an algebro-geometric notion introduced by Kopparty, Moshkovitz, and Zuiddam) are all equal up to an absolute constant. As a corollary, we obtain strong trade-offs on the arithmetic complexity of a biased bilinear map, and on the separation between computing a bilinear map exactly and on average. Our result settles open questions of Haramaty and Shpilka [STOC 2010], and of Lovett [Discrete Anal. 2019] for 3-tensors.
Publié le : 
@article{DAS_2022_a8,
     author = {Alex Cohen and Guy Moshkovitz},
     title = {Structure vs. {Randomness} for {Bilinear} {Maps}},
     journal = {Discrete analysis},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2022_a8/}
}
TY  - JOUR
AU  - Alex Cohen
AU  - Guy Moshkovitz
TI  - Structure vs. Randomness for Bilinear Maps
JO  - Discrete analysis
PY  - 2022
UR  - http://geodesic.mathdoc.fr/item/DAS_2022_a8/
LA  - en
ID  - DAS_2022_a8
ER  - 
%0 Journal Article
%A Alex Cohen
%A Guy Moshkovitz
%T Structure vs. Randomness for Bilinear Maps
%J Discrete analysis
%D 2022
%U http://geodesic.mathdoc.fr/item/DAS_2022_a8/
%G en
%F DAS_2022_a8
Alex Cohen; Guy Moshkovitz. Structure vs. Randomness for Bilinear Maps. Discrete analysis (2022). http://geodesic.mathdoc.fr/item/DAS_2022_a8/