Foundations and Trends® in Theoretical Computer Science > Vol 6 > Issue 1–2

Partial Derivatives in Arithmetic Complexity and Beyond

By Xi Chen, Columbia University, USA, xichen@cs.columbia.edu | Neeraj Kayal, Microsoft Research, India, neeraka@microsoft.com | Avi Wigderson, Institute for Advanced Study, USA, avi@ias.edu

 
Suggested Citation
Xi Chen, Neeraj Kayal and Avi Wigderson (2011), "Partial Derivatives in Arithmetic Complexity and Beyond", Foundations and Trends® in Theoretical Computer Science: Vol. 6: No. 1–2, pp 1-138. http://dx.doi.org/10.1561/0400000043

Publication Date: 10 Sep 2011
© 2011 X. Chen, N. Kayal and A. Wigderson
 
Subjects
Computational complexity,  Cryptography and information security
 

Free Preview:

Download extract

Share

Download article
In this article:
1 Introduction 
Part I: Structure 
2 Symmetries of a Polynomial 
3 Algebraic Independence 
4 Polynomials with High Arithmetic Complexity 
5 Bezout's Theorem 
6 Algebraic Extractors and the Jacobian Conjecture 
7 The "Joints Conjecture" Resolved 
8 The Stepanov Method 
Part II: Lower Bounds 
9 General Arithmetic Circuits 
10 Sums of Powers of Linear Forms 
11 Depth-3 Arithmetic Circuits 
12 Arithmetic Formulae 
13 Projections of Determinant to Permanent 
Part III: Algorithms 
14 Identity Testing 
15 Absolute Irreducibility Testing 
16 Polynomial Equivalence Testing 
Acknowledgments 
References 

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 symmetries), and help us solve various number theoretic, geometric, and combinatorial problems.

DOI:10.1561/0400000043
ISBN: 978-1-60198-480-7
146 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-60198-481-4
146 pp. $200.00
Buy E-book (.pdf)
Table of contents:
1: Introduction
PART I STRUCTURES
2: Symmetries of a polynomial
3: Algebraic independence
4: Polynomials with high arithmetic complexity
5: Bezout's theorem
6: Algebraic extractors and the Jacobian conjecture
7: The "Joints conjecture" resolved
8: The Stepanov method
PART II LOWER BOUNDS
9: General arithmetic circuits
10: Sums of powers of linear forms
11: Depth-3 arithmetic circuits
12: Arithmetic formulae
13: Projections of Determinant to Permanent
PART III ALGORITHMS
14: Identity testing
15: Absolute irreducibility testing
16: Polynomial equivalence testing
Acknowledgements
References

Partial Derivatives in Arithmetic Complexity and Beyond

Polynomials are perhaps the most important family of functions in mathematics. They feature in celebrated results from both antiquity and modern times, like the insolvability by radicals of polynomials of degree ? 5 of Abel and Galois, and Wiles' proof of Fermat's "last theorem". In computer science they feature in, e.g., error-correcting codes and probabilistic proofs, among many applications. The manipulation of polynomials is essential in numerous applications of linear algebra and symbolic computation. Partial Derivatives in Arithmetic Complexity and Beyond is devoted mainly to the study of polynomials from a computational perspective. It illustrates that one can learn a great deal about the structure and complexity of polynomials by studying (some of) their partial derivatives. It also shows that partial derivatives provide essential ingredients in proving both upper and lower bounds for computing polynomials by a variety of natural arithmetic models. It goes on to look at 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 symmetries), and help us solve various number theoretic, geometric, and combinatorial problems. Partial Derivatives in Arithmetic Complexity and Beyond is an invaluable reference for anyone with an interest in polynomials. Many of the chapters in these three parts can be read independently. For the few which need background from previous chapters, this is specified in the chapter abstract.

 
TCS-043