The power of depth 2 circuits over algebras

DOI10.4230/LIPICS.FSTTCS.2009.2333zbMATH Open1248.68262OpenAlexW2147716837MaRDI QIDQ2920144FDOQ2920144

Authors: Chandan Saha, Ramprasad Saptharishi, Nitin Saxena 

Publication date: 24 October 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_e30d.html

Recommendations

• Polynomial identity testing for depth 3 circuits
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• scientific article; zbMATH DE number 7140484
• Deterministic polynomial identity testing in non-commutative models
• Recent results on polynomial identity testing

zbMATH Keywords

local ringsmatrix algebraspolynomial identity testingdepth 3 circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (9)

• On the power of algebraic branching programs of width two
• On the power of algebraic branching programs of width two
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Recent results on polynomial identity testing
• Progress on polynomial identity testing. II
• Parallel identity testing for skew circuits with big powers and applications
• Witnessing matrix identities and proof complexity
• Parallel identity testing for skew circuits with big powers and applications
• Arithmetic circuits: a chasm at depth 3

This page was built for publication: The power of depth 2 circuits over algebras

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