Monotone separations for constant degree polynomials

DOI10.1016/j.ipl.2009.09.003zbMath1206.68145OpenAlexW2020049924MaRDI QIDQ990088

Pavel Hrubeš, Amir Yehudayoff

Publication date: 2 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.09.003

zbMATH Keywords

computational complexityalgebraic complexityarithmetic circuitconstant degreearithmetic formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Homogeneous formulas and symmetric polynomials
• Negation can be exponentially powerful
• On the depth complexity of formulas
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Depth-3 arithmetic circuits over fields of characteristic zero

This page was built for publication: Monotone separations for constant degree polynomials