Séminaires : Séminaire Général de Logique

Equipe(s) : lm,
Responsables :S. Anscombe, A. Khélif, A. Vignati
Email des responsables : sylvy.anscombe@imj-prg.fr, vignati@imj-prg.fr
Salle : 1013
Adresse :Sophie Germain

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion

Orateur(s) Arpita Korwar - Equipe de Logique Mathématique, IMJ-PRG ,
Titre Polynomial Identity Testing of Sum of ROABPs
Horaire15:10 à 16:10
RésumePolynomials 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.
AdresseSophie Germain