TY - GEN
T1 - Testing equivalence of polynomials under shifts
AU - Dvir, Zeev
AU - De Oliveira, Rafael Mendes
AU - Shpilka, Amir
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84904176159&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904176159&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-43948-7_35
DO - 10.1007/978-3-662-43948-7_35
M3 - Conference contribution
AN - SCOPUS:84904176159
SN - 9783662439470
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 417
EP - 428
BT - Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PB - Springer Verlag
T2 - 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
Y2 - 8 July 2014 through 11 July 2014
ER -