Skip to main content

Testing equivalence of polynomials under shifts

Author(s): Dvir, Zeev; De Oliveira, RM; Shpilka, A

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr10m5m
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDvir, Zeev-
dc.contributor.authorDe Oliveira, RM-
dc.contributor.authorShpilka, A-
dc.date.accessioned2018-07-20T15:11:02Z-
dc.date.available2018-07-20T15:11:02Z-
dc.date.issued2014en_US
dc.identifier.citationDvir, Z, De Oliveira, RM, Shpilka, A. (2014). Testing equivalence of polynomials under shifts. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8572 LNCS (417 - 428. doi:10.1007/978-3-662-43948-7_35en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr10m5m-
dc.description.abstractTwo 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.en_US
dc.format.extent417 - 428en_US
dc.language.isoen_USen_US
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.rightsAuthor's manuscripten_US
dc.titleTesting equivalence of polynomials under shiftsen_US
dc.typeConference Articleen_US
dc.identifier.doidoi:10.1007/978-3-662-43948-7_35-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
Testing equivalence of polynomials under shifts.pdf256.91 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.