Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

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

TR16-107 | 17th July 2016
Nathanael Fijalkow

Lower Bounds for Alternating Online Space Complexity

Revisions: 1

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

ISSN 1433-8092 | Imprint