Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Olivier Serre:

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

TR15-104 | 13th May 2015
Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont

Streaming Property Testing of Visibly Pushdown Languages

Revisions: 2

In the context of language recognition, we demonstrate the superiority of streaming property testers against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum et al, a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs ... more >>>

ISSN 1433-8092 | Imprint