A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomialsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 11 декабря 2015 г.
Аннотация:This work suggests a method for deriving lower bounds for the complexity of polynomials with positive real coefficients implemented by circuits of functional elements over the monotone arithmetic basis {x+y,x*y}U{a*x|a>0}. Using this method, several new results are obtained. In particular, we construct examples of polynomials of degree m-1 in each of the n variables with coefficients 0 and 1 having additive monotone complexity m^{(1-o(1))n} and multiplicative monotone complexity m^{(1/2-o(1))n} as m^n grows. In this form, the lower bounds derived here are sharp.