About me
I am an Assistant Professor in the Talgo (Theory, ALgorithms, Graphs, and Optimization) team at the Computer Science Department of École normale supérieure, Paris, France. I am interested in algorithms on strings, small-space algorithms and data structures, streaming algorithms, property testing algorithms, lower bounds, and communication complexity.
Short bio
- Assistant Professor, École normale supérieure, Paris, France, 2017-up to date
- Postdoc, Université Paris-Diderot, Paris, France, 2016-2017
- Research Associate, University of Bristol, Bristol, UK, 2015-2016
- Assistant Professor, Department of Computer Science, Higher School of Economics, Moscow, Russia, 2013-2015
- Ph.D. in Mathematics, Lomonosov Moscow State University, Moscow, Russia, 2013
- M.Sc. in Data Science, Moscow Institute of Physics and Technology and Yandex School of Data Analysis, Moscow, Russia, 2009
- M.Sc. in Mathematics, Lomonosov Moscow State University, Moscow, Russia, 2009
PhD supervision
I am currently co-supervising G. Gourdel with P. Peterlongo and Gabriel Bathie with N. Fijalkow.
Current projects
2021-2024 PARSe (ANR-20-CE48-0001): Approximation and Randomised String Processing, PI
2020-2023 AlgoriDAM (ANR-19-CE48-0016): Algorithmic theory of new data models
Programme committee work
I co-chaired CPM 2021 with P. Gawrychowski.
I was honored to serve on the program committees of: ICALP 2020, SOSA 2020, CPM 2019, CPM 2018, CPM 2017, SPIRE 2017, IWOCA 2016, CSR 2016, SPIRE 2015, CPM 2015, CPM 2014.
Selected publications
- An Improved Algorithm for The k-Dyck Edit Distance Problem with D. Fried, S. Golan, T. Kociumaka, T. Kopelowitz, E. Porat. In the ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).
- Streaming Regular Expression Membership and Pattern Matching with B. Dudek, P. Gawrychowski, G. Gourdel. In the ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).
- Small space and streaming pattern matching with k edits with T. Kociumaka and E. Porat. In the Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021).
- All non-trivial variants of 3-LDT are equivalent. with B. Dudek and Paweł Gawrychowski, in the ACM Symposium on Theory of Computing (STOC 2020).
- Lower bounds for text indexing with mismatches and differences. with V. Cohen-Addad and L. Feuilloley, in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).
- Improved bounds for testing Dyck languages with E. Fischer and F. Magniez, in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
- The k-mismatch problem revisited with R. Clifford, A. Fontaine, E. Porat, B. Sach, in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2016).
- Wavelet Trees Meet Suffix Trees with M. Babenko, P. Gawrychowski, T. Kociumaka, in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).