Structure vs. randomness for bilinear maps
Structure vs. randomness for bilinear maps
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.
Published version for Discrete Analysis
- City University of New York United States
- Yale University United States
- Bard College United States
- King’s University United States
- CUNY Baruch College United States
FOS: Computer and information sciences, 68R05, 15A69, Networks and circuits as models of computation; circuit complexity, bilinear complexity, Combinatorics in computer science, Computational Complexity (cs.CC), Secant varieties, tensor rank, varieties of sums of powers, Computer Science - Computational Complexity, Mathematics - Algebraic Geometry, tensors, Multilinear algebra, tensor calculus, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Algebraic Geometry (math.AG), Mathematics, algebraic geometry
FOS: Computer and information sciences, 68R05, 15A69, Networks and circuits as models of computation; circuit complexity, bilinear complexity, Combinatorics in computer science, Computational Complexity (cs.CC), Secant varieties, tensor rank, varieties of sums of powers, Computer Science - Computational Complexity, Mathematics - Algebraic Geometry, tensors, Multilinear algebra, tensor calculus, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Algebraic Geometry (math.AG), Mathematics, algebraic geometry
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).5 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!