scientific article; zbMATH DE number 7204375

DOI10.4230/LIPICS.MFCS.2017.41MaRDI QIDQ5111256zbMATH OpenFDO

Authors Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

Publication date 26 May 2020

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)

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

Cites work

• scientific article; zbMATH DE number 7204375 (Why is no real title available?)
• scientific article; zbMATH DE number 7140484 (Why is no real title available?)
• A super-polynomial lower bound for regular arithmetic formulas
• Algebras with Polynomial Identities and Computing the Determinant
• An exponential lower bound for homogeneous depth four arithmetic formulas
• Approaching the chasm at depth four
• Arithmetic circuits and the Hadamard product of polynomials
• Arithmetic circuits: a survey of recent results and open questions
• Characterizing Valiant's algebraic complexity classes
• Clifford algebras and approximating the permanent
• Depth-3 arithmetic circuits over fields of characteristic zero
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Deterministic polynomial identity testing in non-commutative models
• Lower bounds for depth-4 formulas computing iterated matrix multiplication
• Lower bounds for non-commutative skew circuits
• Lower bounds on arithmetic circuits via partial derivatives
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Non-commutative circuits and the sum-of-squares problem
• Non-commutative computations: lower bounds and polynomial identity testing
• Randomized polynomial time identity testing for noncommutative circuits
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
• The complexity of bounded register and skew arithmetic computation

Cited in

(5)

• scientific article; zbMATH DE number 7204375 (Why is no real title available?)
• scientific article; zbMATH DE number 7650909 (Why is no real title available?)
• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• scientific article; zbMATH DE number 7561311 (Why is no real title available?)
• 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)