Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-038 | 21st February 2018 12:28

Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees


Authors: Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann
Publication: 22nd February 2018 13:44
Downloads: 1158


This paper studies lower bounds for arithmetic circuits computing (non-commutative) polynomials. Our conceptual contribution is an exact correspondence between circuits and weighted automata: algebraic branching programs are captured by weighted automata over words, and circuits with unique parse trees by weighted automata over trees.

The key notion for understanding the minimisation question of weighted automata is the Hankel matrix: the rank of the Hankel matrix of a word or tree series is exactly the size of the smallest weighted automaton recognising this series. For automata over words, the correspondence we establish allows us to rephrase Nisan's celebrated tight bounds for algebraic branching programs. We extend this result by considering automata over trees and obtain the first tight bounds for all circuits with unique parse trees.

ISSN 1433-8092 | Imprint