Evènement pour le 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. 
OrateurPierre Ohlmann 
UrlIRIF, Paris 7 

Aucun document lié à cet événement.

Retour à l'index