### Monotone separations for constant degree polynomials.Monotone separations for constant degree polynomials.

Access Restriction
Open

 Author Yehudayoff, Amir Source CiteSeerX Content type Text File Format PDF
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Monotone Separation ♦ Constant Degree Polynomial ♦ Constant Degree ♦ Homogeneous Arithmetic Formula ♦ General Arithmetic Formula ♦ Monotone Formula ♦ Homogeneous Formula ♦ Upper Bound Abstract We prove a separation between monotone and general arithmetic formulas for polynomials of constant degree. We give an example of a polynomial C in n vari-ables and degree k which is computable by a homogeneous arithmetic formula of size O(k2n2), but every monotone formula computing C requires size (n/kc)Ω(log k), with c ∈ (0, 1). Since the upper bound is achieved by a homogeneous arithmetic formula, we also obtain a separation between monotone and homogeneous formulas, for polynomials of constant degree. 1 Educational Role Student ♦ Teacher Age Range above 22 year Educational Use Research Education Level UG and PG ♦ Career/Technical Study