Testing equivalence of polynomials under shifts

Zeev Dvir, Rafael Mendes De Oliveira, Amir Shpilka

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

10 Scopus citations

Abstract

Two polynomials f, g ∈ double-struck F[x1...,xn] are called shift-equivalent if there exists a vector (a1..., a n ∈ double-struck Fn such that the polynomial identity f(x1+a1,...,xn+an) ≡g(x1,...,xn) holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our algorithm runs in time polynomial in the circuit size of the polynomials, to which it is given black box access. This complements a previous work of Grigoriev [Gri97 who gave a deterministic algorithm running in time nO(d) for degree d polynomials. Our algorithm uses randomness only to solve instances of the Polynomial Identity Testing (PIT) problem. Hence, if one could de-randomize PIT (a long-standing open problem in complexity) a de-randomization of our algorithm would follow. This establishes an equivalence between de-randomizing shift-equivalence testing and de-randomizing PIT (both in the black-box and the white-box setting). For certain restricted models, such as Read Once Branching Programs, we already obtain a deterministic algorithm using existing PIT results.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PublisherSpringer Verlag
Pages417-428
Number of pages12
EditionPART 1
ISBN (Print)9783662439470
DOIs
StatePublished - Jan 1 2014
Event41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark
Duration: Jul 8 2014Jul 11 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8572 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
CountryDenmark
CityCopenhagen
Period7/8/147/11/14

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Testing equivalence of polynomials under shifts'. Together they form a unique fingerprint.

  • Cite this

    Dvir, Z., De Oliveira, R. M., & Shpilka, A. (2014). Testing equivalence of polynomials under shifts. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings (PART 1 ed., pp. 417-428). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8572 LNCS, No. PART 1). Springer Verlag. https://doi.org/10.1007/978-3-662-43948-7_35