Files and links (1)
Published, Version of Record (VoR)CC BY V4.0, Open
Journal article
On Cap Sets and the Group-theoretic Approach to Matrix Multiplication
Discrete analysis, v 3(2017)
01 Jan 2017
Abstract
In 2003, Cohn and Umans described a framework for proving upper bounds on the exponent omega of matrix multiplication by reducing matrix multiplication to group algebra multiplication, and in 2005 Cohn, Kleinberg, Szegedy, and Umans proposed specific conjectures for how to obtain omega = 2. In this paper we rule out obtaining omega = 2 in this framework from abelian groups of bounded exponent. To do this we bound the size of tricolored sum-free sets in such groups, extending the breakthrough results of Croot, Lev, Pach, Ellenberg, and Gijswijt on cap sets. As a byproduct of our proof, we show that a variant of tensor rank due to Tao gives a quantitative understanding of the notion of unstable tensor from geometric invariant theory.
Metrics
Details
- Title
- On Cap Sets and the Group-theoretic Approach to Matrix Multiplication
- Creators
- Jonah Blasiak - Drexel Univ, Dept Math, Philadelphia, PA 19104 USAThomas Church - Stanford Univ, Dept Math, 450 Serra Mall, Stanford, CA 94305 USAHenry Cohn - Microsoft Res New England, One Mem Dr, Cambridge, MA 02142 USAJoshua A. Grochow - Univ Colorado Boulder, Dept Comp Sci, 1111 Engn Dr, Boulder, CO 80309 USAEric Naslund - Princeton Univ, Math Dept, Fine Hall,Washington Rd, Princeton, NJ 08544 USAWilliam F. Sawin - Swiss Fed Inst Technol, ETH Inst Theoret Studies, CH-8092 Zurich, SwitzerlandChris Umans - CALTECH, Comp & Math Sci, 1200 E Calif Blvd, Pasadena, CA 91125 USADrexel University
- Publication Details
- Discrete analysis, v 3(2017)
- Publisher
- Alliance Diamond Open Access Journals
- Number of pages
- 27
- Grant note
- 279438 / Ben Green's ERC Starting Grant 1350138 / Division Of Mathematical Sciences; National Science Foundation (NSF); NSF - Directorate for Mathematical & Physical Sciences (MPS) ETH Zurich Foundation; ETH Zurich DMS-14071174; DMS-1350138; DGE-1148900; CCF-1423544 / NSF; National Science Foundation (NSF) Walter Haefner Foundation Alfred P. Sloan Foundation Frederick E. Terman Fellowship Simons Foundation Investigator grant Santa Fe Institute Omidyar Fellowship
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000463268100003
- Scopus ID
- 2-s2.0-85032479699
- Other Identifier
- 991019168376004721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Industry collaboration
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Mathematics