scientific article; zbMATH DE number 7204375

DOI10.4230/LIPICS.MFCS.2017.41zbMATH Open1441.68041MaRDI QIDQ5111256FDOQ5111256

Guillaume Lagarde, Srikanth Srinivasan, Nutan Limaye

Publication date: 26 May 2020

Title of this publication is not available (Why is that?)

Recommendations

• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Lower bounds on monotone arithmetic circuits with restricted depths
• On lower bounds for multiplicative circuits and linear circuits in noncommutative domains
• Lower bounds on arithmetic circuits via partial derivatives
• Lower bounds for monotone arithmetic circuits via communication complexity
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains

zbMATH Keywords

partial derivativesrestrictionsnoncommutative arithmetic circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Characterizing Valiant's algebraic complexity classes
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Lower bounds on arithmetic circuits via partial derivatives
• Deterministic polynomial identity testing in non-commutative models
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• Arithmetic Circuits: A survey of recent results and open questions
• Title not available (Why is that?)
• Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits
• A super-polynomial lower bound for regular arithmetic formulas
• Approaching the Chasm at Depth Four
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Depth-3 arithmetic circuits over fields of characteristic zero
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Arithmetic circuits and the Hadamard product of polynomials
• Clifford algebras and approximating the permanent
• Non-commutative circuits and the sum-of-squares problem
• Algebras with Polynomial Identities and Computing the Determinant
• Title not available (Why is that?)
• Lower bounds for non-commutative skew circuits
• Title not available (Why is that?)
• The Complexity of Bounded Register and Skew Arithmetic Computation
• Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication
• Randomized polynomial time identity testing for noncommutative circuits
• Title not available (Why is that?)

Cited In (5)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• Title not available (Why is that?)
• Non-commutative arithmetic circuits: depth reduction and size lower bounds

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 Q5111256)