scientific article; zbMATH DE number 7250151

DOI10.4230/LIPICS.CCC.2018.11MaRDI QIDQ5121899zbMATH OpenFDO

Authors Noga Alon, Mrinal Kumar, Ben Lee Volk

Publication date 22 September 2020

Full work available at URL https://arxiv.org/abs/1708.02037

zbMATH Keywords

algebraic complexitycircuit lower boundsmultilinear circuits

Mathematics Subject Classification ID

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

Recommendations

• Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Balancing syntactically multilinear arithmetic circuits
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• An almost cubic lower bound for depth three arithmetic circuits

Cites work

• A Lower Bound for the Formula Size of Rational Functions
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• A quadratic lower bound for homogeneous algebraic branching programs
• Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
• Approaching the chasm at depth four
• Arithmetic circuits: a survey of recent results and open questions
• Balancing sets of vectors
• Balancing sets of vectors
• Balancing syntactically multilinear arithmetic circuits
• Codes with given distances
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Efficient balanced codes
• Elusive functions and lower bounds for arithmetic circuits
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• Fast Parallel Matrix Inversion Algorithms
• Forbidden Intersections
• Gröbner bases for complete uniform families
• scientific article; zbMATH DE number 1332669 (Why is no real title available?)
• scientific article; zbMATH DE number 1775446 (Why is no real title available?)
• scientific article; zbMATH DE number 7204282 (Why is no real title available?)
• Lower bounds and separations for constant depth multilinear circuits
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• Lower bounds on arithmetic circuits via partial derivatives
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Partial derivatives in arithmetic complexity and beyond
• Separation of multilinear circuit and formula size
• Shattering news
• The complexity of partial derivatives
• The probabilistic method

Cited in

(13)

• Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
• Balancing syntactically multilinear arithmetic circuits
• \(d\)-Galvin families
• Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
• Some lower bound results for set-multilinear arithmetic computations
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Resource trade-offs in syntactically multilinear arithmetic circuits
• Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
• Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
• Lower bounds for multilinear order-restricted ABPs
• A super-quadratic lower bound for depth four arithmetic circuits
• Lower bounds for special cases of syntactic multilinear ABPs
• A robust version of Hegedűs's lemma, with applications

Describes a project that uses

Uses Software

• lowerbounds-survey
• GitHub

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5121899)