Cyclotomic Identity Testing and Applications

We consider the cyclotomic identity testing (CIT) problem: given a polynomial~, decide whether is zero, where is a primitive complex -th root of unity and are integers, represented in binary. When~ 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 is given by a circuit of polynomially bounded degree, we give a randomized {\NC} algorithm. In case 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, where is a linear form and 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~ 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}. This is joint work with Sylvain Perifel, Mahsa Shirmohammadi and James Worrell, to be presented at ISSAC 2021.

Authors

• Nikhil Balaji

Keywords

No keywords are indexed for this paper.