Monotone separations for constant degree polynomials

DOI10.1016/J.IPL.2009.09.003MaRDI QIDQ990088zbMATH OpenOpenAlexFDO

Authors 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 complexityarithmetic circuitalgebraic complexityconstant degreearithmetic formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Strongly Exponential Separation between Monotone VP and Monotone VNP
• Homogeneous formulas and symmetric polynomials
• Separation of multilinear circuit and formula size
• scientific article; zbMATH DE number 7166711
• On Lower Bounds for Constant Width Arithmetic Circuits

Cites work

• scientific article; zbMATH DE number 5485585 (Why is no real title available?)
• Depth-3 arithmetic circuits over fields of characteristic zero
• 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

Cited in

(3)

• Separation of the monotone NC hierarchy
• Log-concavity and lower bounds for arithmetic circuits
• Homogeneous formulas and symmetric polynomials

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

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