Cyclotomic Identity Testing and Applications
share
We consider the cyclotomic identity testing (CIT) problem: given a polynomial f(x_1,…,x_k), decide whether f(ζ_n^e_1,…,ζ_n^e_k) is zero, where ζ_n = e^2π i/n is a primitive complex n-th root of unity and e_1,…,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=∑_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.
READ FULL TEXT