On sunflowers and matrix multiplication

DOI10.1007/s00037-013-0060-1zbMath1268.05223OpenAlexW2170795229MaRDI QIDQ354642

Christopher Umans, Amir Shpilka, Noga Alon

Publication date: 19 July 2013

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.9339

zbMATH Keywords

matrix multiplicationsunflower conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal set theory (05D05) Other classical set theory (including functions, relations, and set algebra) (03E20)

Related Items

UPPER BOUNDS FOR SUNFLOWER-FREE SETS, Popular progression differences in vector spaces II, The analytic rank of tensors and its applications, Universal points in the asymptotic spectrum of tensors, On Sidon sets and asymptotic bases, Multicolour Sunflowers, New applications of the polynomial method: The cap set conjecture and beyond, An introduction to the computational complexity of matrix multiplication, Sunflowers and testing triangle-freeness of functions, Unnamed Item, Fast matrix multiplication and its algebraic neighbourhood, On cap sets and the group-theoretic approach to matrix multiplication, An initial study of time complexity in infinite-domain constraint satisfaction, Erdős-Ginzburg-Ziv constants by avoiding three-term arithmetic progressions, Caps and progression-free sets in \(\mathbb{Z}_m^n\), Maximum subsets of \(\mathbb{F}^n_q\) containing no right angles, Unnamed Item, On the size of subsets of \(\mathbb{F}_p^n\) without \(p\) distinct elements summing to zero, Frankl-Rödl-type theorems for codes and permutations, Unnamed Item, Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication, Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• The monotone circuit complexity of Boolean functions
• On the combinatorial problems which I would most like to see solved
• Combinatorial properties of systems of sets
• Intersection statements for systems of sets
• Extensions of generalized product caps
• On subsets of finite Abelian groups with no 3-term arithmetic progressions
• Gaussian elimination is not optimal
• New bounds on cap sets
• Intersection Theorems for Systems of Sets
• Relative bilinear complexity and matrix multiplication.
• Intersection Theorems for Systems of Sets
• Multiplying matrices faster than coppersmith-winograd
• Intersection Theorems for Systems of Sets (II)
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression