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

Equipe(s) : lm,
Responsables :O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, C. Sureson
Email des responsables :
Salle : salle 2015
Adresse :Sophie Germain
Description

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
Date20/03/2017
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.
Sallesalle 2015
AdresseSophie Germain
© IMJ-PRG