Deterministic Divisibility Testing via Shifted Partial Derivatives

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Kayal has recently introduced the method of shifted partial derivatives as a way to give the first exponential lower bound for computing an explicit polynomial as a sum of powers of constant-degree polynomials. This method has garnered further attention because of the work of Gupta, Kamath, Kayal and Saptharishi who used this method to obtain lower bounds that approach the 'chasm at depth-4'. In this work, we investigate to what extent this method can be used to obtain deterministic polynomial identity testing (PIT) algorithms, which are algorithms that decide whether a given algebraic circuit computes the zero polynomial. In particular, we give a poly(s)(log s)-time deterministic black-box PIT algorithm for a size-s sum of powers of constant-degree polynomials. This is the first sub-exponential deterministic PIT algorithm for this model of computation and the first PIT algorithm based on the method of shifted partial derivatives. We also study the problem of divisibility testing, which when given multivariate polynomials f and g (as algebraic circuits) asks to decide whether f divides g. Using Strassen's technique for the elimination of divisions, we show that one can obtain deterministic divisibility testing algorithms via deterministic PIT algorithms, and this reduction does not dramatically increase the complexity of the underlying algebraic circuits. Using this reduction, we show that deciding divisibility of a constant-degree polynomial f into a sparse polynomial g reduces to PIT of sums of a monomial multiplied by a power of constant-degree polynomials. We then extend the method of shifted partial derivatives to give a poly(s)(log s)-time deterministic black-box PIT algorithm for this model of computation, and thus derive a corresponding deterministic divisibility algorithm. This is the first non-trivial deterministic algorithm for this problem. Previous work on multivariate divisibility testing due to Saha, Saptharishi and Saxena gave algorithms for when f is linear and g is sparse, and essentially worked via PIT algorithms for read-once (oblivious) algebraic branching programs (roABPs). We give explicit sums of powers of quadratic polynomials that require exponentially-large roABPs in a strong sense, showing that techniques known for roABPs have limited applicability in our regime. Finally, by combining our results with the algorithm of Forbes, Shpilka and Saptharishi we obtain poly(s)(log log s)-time deterministic black-box PIT algorithms for various models (translations of sparse polynomials, and sums of monomials multiplied by a power of a linear polynomial) where only poly(s) (Theta(log s))-time such algorithms were previously known.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PublisherIEEE Computer Society
Pages451-465
Number of pages15
Volume2015-December
ISBN (Electronic)9781467381918
DOIs
StatePublished - Dec 11 2015
Externally publishedYes
Event56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States
Duration: Oct 17 2015Oct 20 2015

Other

Other56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
CountryUnited States
CityBerkeley
Period10/17/1510/20/15

Keywords

  • divisibility testing
  • polynomial identity testing
  • read-once algebraic branching programs
  • shifted partial derivatives
  • sparse polynomials

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Deterministic Divisibility Testing via Shifted Partial Derivatives'. Together they form a unique fingerprint.

  • Cite this

    Forbes, M. A. (2015). Deterministic Divisibility Testing via Shifted Partial Derivatives. In Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 (Vol. 2015-December, pp. 451-465). [7354409] IEEE Computer Society. https://doi.org/10.1109/FOCS.2015.35