Cyclotomic Identity Testing and Applications
Autor: | James Worrell, Nikhil Balaji, Mahsa Shirmohammadi, Sylvain Perifel |
---|---|
Přispěvatelé: | Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) |
Rok vydání: | 2021 |
Předmět: |
Computer Science - Symbolic Computation
FOS: Computer and information sciences Polynomial Root of unity Polynomial identity testing 010102 general mathematics Zero (complex analysis) 0102 computer and information sciences Computational Complexity (cs.CC) Symbolic Computation (cs.SC) 01 natural sciences Combinatorics Computer Science - Computational Complexity Integer 010201 computation theory & mathematics Cyclotomic identity [INFO]Computer Science [cs] 0101 mathematics Algebraic number Time complexity ComputingMilieux_MISCELLANEOUS Mathematics |
Zdroj: | ISSAC ISSAC '21: International Symposium on Symbolic and Algebraic Computation ISSAC '21: International Symposium on Symbolic and Algebraic Computation, Jul 2021, Virtual Event Russian Federation, France. pp.35-42, ⟨10.1145/3452143.3465530⟩ |
DOI: | 10.1145/3452143.3465530 |
Popis: | We consider the cyclotomic identity testing (CIT) problem: given a polynomial $f(x_1,\ldots,x_k)$, decide whether $f(\zeta_n^{e_1},\ldots,\zeta_n^{e_k})$ is zero, where $\zeta_n = e^{2\pi i/n}$ is a primitive complex $n$-th root of unity and $e_1,\ldots,e_k$ are integers, represented in binary. When $f$ is given by an algebraic circuit, we give a randomized polynomial-time algorithm for CIT assuming the generalised Riemann hypothesis (GRH), and show that the problem is in coNP unconditionally. When $f$ is given by a circuit of polynomially bounded degree, we give a randomized NC algorithm. In case $f$ is a linear form we show that the problem lies in NC. Towards understanding when CIT can be solved in deterministic polynomial-time, we consider so-called diagonal depth-3 circuits, i.e., polynomials $f=\sum_{i=1}^m g_i^{d_i}$, where $g_i$ is a linear form and $d_i$ a positive integer given in unary. We observe that a polynomial-time algorithm for CIT on this class would yield a sub-exponential-time algorithm for polynomial identity testing. However, assuming GRH, we show that if the linear forms~$g_i$ are all identical then CIT can be solved in polynomial time. Finally, we use our results to give a new proof that equality of compressed strings, i.e., strings presented using context-free grammars, can be decided in randomized NC. |
Databáze: | OpenAIRE |
Externí odkaz: |