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

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

Archives


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
Diffusion
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.
Salle1013
AdresseSophie Germain
© IMJ-PRG