|
Evènement pour le groupe Séminaire Méthodes Formelles
Date | 2018-04-17 11:00-12:00 |
Titre | Arithmetic 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. |
Lieu | 178 |
Orateur | Pierre Ohlmann |
Email | pierre.ohlmann@ens-lyon.fr |
Url | IRIF, Paris 7 |
Aucun document lié à cet événement. RetourRetour à l'index
| |