“Resistant” Polynomials and Stronger Lower Bounds for Depth-Three Arithmetical Formulas

DOI10.1007/978-3-540-73545-8_46zbMATH Open1213.68333OpenAlexW1581025509MaRDI QIDQ3608871FDOQ3608871

Authors: Maurice Jansen, Kenneth W. Regan 

Publication date: 6 March 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73545-8_46

Recommendations

• Depth-3 arithmetic circuits over fields of characteristic zero
• Lower bounds for depth three arithmetic circuits with small bottom fanin
• An almost cubic lower bound for depth three arithmetic circuits
• Tensor-rank and lower bounds for arithmetic formulas
• Tensor-rank and lower bounds for arithmetic formulas

zbMATH Keywords

computational complexitypartial derivativeslower boundsarithmetical circuitsconstant depth formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: “Resistant” Polynomials and Stronger Lower Bounds for Depth-Three Arithmetical Formulas

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