Access Restriction

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