Paper Info
Title
A hitting set construction, with application to arithmetic circuit lower bounds
Abstract
Abstract. A polynomial identity testing algorithm must,determine whether a given input polynomial is identically equal to 0. We give a deterministic black-box identity testing algorithm for polynomials of the form P,, and from there we derive a lower bound for representations of univariate polynomials under this form. This shows that the “hardness from derandomization” approach to lower bounds is feasible for a restricted class of arithmetic circuits.
Year
Venue
Keywords
2009
Clinical Orthopaedics and Related Research
lower bound,computational complexity
Field
DocType
Volume
Polynomial identity testing,Discrete mathematics,Combinatorics,Algebraic number,Exponential function,Polynomial,Upper and lower bounds,Univariate,Arithmetic circuit complexity,Mathematics,Algebraic number theory
Journal
abs/0907.5
Citations 
PageRank 
References 
1
0.42
14
Authors
1
Name
Order
Citations
PageRank
Pascal Koiran1919113.85