|Responsables :||O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, C. Sureson|
|Email des responsables :|
|Salle :||salle 2015|
|Adresse :||Sophie Germain|
|Orateur(s)||Arpita Korwar - Equipe de Logique Mathématique, IMJ-PRG ,|
|Titre||Polynomial Identity Testing of Sum of ROABPs|
|Horaire||15:10 à 16:10|
|Résume||Polynomials are fundamental objects in mathematics. Though univariate polynomials are fairly well-understood, multivariate polynomials are not. Arithmetic circuits are the primary tool used to study the complexity of polynomials in computer science. They allow for the classification of polynomials according to their complexity.
Polynomial identity testing (PIT) asks if a polynomial, input in the form of an arithmetic circuit, is identically zero.
One special kind of arithmetic circuits are read-once arithmetic branching programs (ROABPs), which can be written as a product of univariate polynomial matrices over distinct variables.
We will be studying the characterization of an ROABP. In the process, we can give a polynomial-time PIT for the sum of constantly many ROABPs.