All reports by Author Nathanael Fijalkow:

__
TR18-180
| 3rd November 2018
__

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre#### Lower bounds for arithmetic circuits via the Hankel matrix

__
TR18-038
| 21st February 2018
__

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann#### Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees

__
TR16-107
| 17th July 2016
__

Nathanael Fijalkow#### Lower Bounds for Alternating Online Space Complexity

Revisions: 1

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre

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

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann

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

Nathanael Fijalkow

The notion of online space complexity, introduced by Karp in 1967, quantifies the amount of states required to solve a given problem using an online algorithm,

represented by a machine which scans the input exactly once from left to right.

In this paper, we study alternating machines as introduced by ...
more >>>