scientific article; zbMATH DE number 7250151
From MaRDI portal
Publication:5121899
DOI10.4230/LIPIcs.CCC.2018.11zbMath1441.68038arXiv1708.02037MaRDI QIDQ5121899
Noga Alon, Ben lee Volk, Mrinal Kumar
Publication date: 22 September 2020
Full work available at URL: https://arxiv.org/abs/1708.02037
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
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 (7)
Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Unnamed Item ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ \(d\)-Galvin families ⋮ Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree ⋮ Towards Optimal Depth Reductions for Syntactically Multilinear Circuits ⋮ A super-quadratic lower bound for depth four arithmetic circuits
Uses Software
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
- 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
- Partial Derivatives in Arithmetic Complexity and Beyond
- 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
- 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:
