Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Parse Trees:
TR18-180 | 3rd November 2018
Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre

Lower bounds for arithmetic circuits via the Hankel matrix

We study the complexity of representing polynomials by arithmetic circuits in both the commutative and the non-commutative settings. Our approach goes through a precise understanding of the more restricted setting where multiplication is not associative, meaning that we distinguish $(xy)z$ from $x(yz)$.

Our first and main conceptual result is a ... more >>>

ISSN 1433-8092 | Imprint