Personal page of Nathanaël François


Personal page of Nathanaël François

Since October 2015, I am doing a post-doctorate under the supervision of Christian Sohler in the Fakultät für Informatik of the Technische Universität Dortmund.


CV: in French or in English.

Research interests

My main research interests are in lower and upper bounds for complexity of sublinear algorithms, which include streaming algorithms, communication protocols, and query-based property testing.

The data structures I have worked with include priority queues, visibly push-down languages, and bounded-degree expander graphs.

Ph.D. thesis

I did my Ph.D., titled Algorithms and lower bounds in variants of the streaming model, under the supervision of Frédéric Magniez at LIAFA in Université Paris Diderot. I defended on September 2, 2015. The manuscript is available here.


Streaming Property Testing of Visibly Pushdown Languages [proceedings, arXiv], with Frédéric Magniez, Michel de Rougemont, and Olivier Serre.

Unidirectional Input/Output Streaming Complexity of Reversal and Sorting, RANDOM 2014 [proceedings, arXiv], with Rahul Jain and Frédéric Magniez.

Streaming complexity of checking priority queues, STACS 2013 [proceedings, arXiv], with Frédéric Magniez.