Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Partial Derivatives in Arithmetic Complexity and beyond

Xi Chen, Neeraj Kayal, and Avi Wigderson

Abstract

How complex is a given multivariate polynomial? The main point of this survey is that one can learn a great deal about the structure and complexity of polynomials by studying (some of) their partial derivatives. The bulk of the survey shows that partial derivatives provide essential ingredients in proving both upper and lower bounds for computing polynomials by a variety of natural arithmetic models.

We will also see applications which go beyond computational complexity, where partial derivatives provide a wealth of structural information about polynomials (including their number of roots, reducibility and internal symmteries), and help also solve various number theoretic, geometric, and combinatorial problems.

Details

Publication typeArticle
Published inFoundations and Trends in Theoretical Computer Science
PublisherNOW Publishers
> Publications > Partial Derivatives in Arithmetic Complexity and beyond