Аннотация:
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 (a recently introduced algebro-geometric notion) are all equivalent up to an absolute constant. The proof uses tools from algebraic geometry to argue about tangent spaces to certain determinantal varieties corresponding to the tensor. Our result settles open questions of Haramaty and Shpilka [STOC 2010], and of Lovett [Discrete Anal., 2019] for 3-tensors.
Joint work with Guy Moshkovitz.
