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

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

© 2011 X. Chen, N. Kayal and A. Wigderson

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

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.

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

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.