Fall 2018

Formal Series and Non-Commutative Computations

Thursday, Dec. 6, 2018 12:00 pm12:30 pm PST

Add to Calendar


Guillaume Malod (Université Paris Diderot)

This talk will be inspired by the recently noticed connection [0] between formal (tree) series and non-commutative computations, as a generalization of Nisan's characterization [1] and subsequent results. This provides a clearer understanding of non-commutative computations, possible research directions for general non-commutative circuits and even commutative computations. [0] Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann: Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees. Electronic Colloquium on Computational Complexity (ECCC) 25: 38 (2018)