Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Arithmetic circuits as automata, and applications
du groupe Séminaire Méthodes Formelles

Date 2018-04-17  11:00-12:00
TitreArithmetic circuits as automata, and applications 
RésuméWe give a syntactic correspondence between non-associative arithmetic circuits and acyclic weighted tree automata. We may then export results from automata theory to non-associative circuits and characterize the size of a minimal circuit for a given polynomial as the rank of a Hankel matrix. We will then show how this can be used to re-obtain Nisan's theorem on Algebraic Branching Programs as well as recent results on Unique Parse Tree circuits. Lastly, we will highlight a new way of obtaining lower bounds for general (associative) arithmetic circuits. 
Lieu178 
OrateurPierre Ohlmann 
Emailpierre.ohlmann@ens-lyon.fr 
UrlIRIF, Paris 7 



Aucun document lié à cet événement.

Retour
Retour à l'index