Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits

DOI10.1007/S00493-019-4009-0zbMath1488.68027OpenAlexW3009759485MaRDI QIDQ2204092

Ben lee Volk, Noga Alon, Mrinal Kumar

Publication date: 2 October 2020

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8879/

zbMATH Keywords

lower bound on the sizesyntactically multilinear arithmetic circuit

Mathematics Subject Classification ID

Extremal set theory (05D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (2)

\(L\)-balancing families ⋮ Limitations of sums of bounded read formulas and ABPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds and separations for constant depth multilinear circuits
• On computing the determinant in small parallel time using a small number of processors
• Codes with given distances
• The complexity of partial derivatives
• Shattering news
• Lower bounds on arithmetic circuits via partial derivatives
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• Gröbner bases for complete uniform families
• Balancing syntactically multilinear arithmetic circuits
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• The Difference Between Consecutive Primes, II
• Arithmetic Circuits: A survey of recent results and open questions
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• A Lower Bound for the Formula Size of Rational Functions
• Efficient balanced codes
• Forbidden Intersections
• Fast Parallel Matrix Inversion Algorithms
• Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications
• A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• Approaching the Chasm at Depth Four
• Balancing sets of vectors
• Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Balancing sets of vectors

This page was built for publication: Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits