Abstract

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)

Video Recording