Résumé | We consider the cyclotomic identity testing (CIT) problem: given a polynomial f(x_1,...,x_k),
decide whether f(zeta_n^{e_1},...,zeta_n^{e_k}) is zero, where zeta_n = e^{2pi i/n} is a primitive complex n-th root of unity and e_1,...,e_k are integers, represented in binary.
In case f is given by an algebraic circuit we give a randomized polynomial-time algorithm for CIT. 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 the generalised Riemann hypothesis, 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.
This work is in collaboration with Nikhil Balaji, Sylvain Perifel and James Worrell.
Recording: https://u-bordeaux-fr.zoom.us/rec/share/-NGKM1iAWimIjdg2pXceRQv83jQMN-StdegWO13IwPJwZ6tURH4fu4IgeFfDD027.HiQiIQxJ5uFUM_N9 |