Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Pierre Ohlmann:

TR18-038 | 21st February 2018
Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann

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

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 ... more >>>

ISSN 1433-8092 | Imprint