Evènement pour le groupe Séminaire Méthodes Formelles


Date 2021-04-27  07:00-07:00
TitreCyclotomic Identity Testing and Application 
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 
LieuOnline 
OrateurMahsa Shirmohammadi 
Emailhttps://www.irif.fr/~mahsa/ 
UrlIRIF 



Aucun document lié à cet événement.

Retour
Retour à l'index