Tatiana Starikovskaya

Tatiana Starikovskaya

Assistant Professor
(Maître de Conférences)

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

Current PhD students:

I am currently co-supervising T. El Ghazi with Chien-Chung Huang.

Defended PhD students:

Garance Gourdel (October 2023, co-supervised with P. Peterlongo)

Gabriel Bathie (June 2025, co-supervised with N. Fijalkow)

Funding projects

2021-2025 PARSe (ANR-20-CE48-0001): Approximation and Randomised String Processing, PI

Editor and Programme committee work

I have been an editor of Theoretical Computer Science journal since 2026.

I was honoured to serve on the program committees of: ESA 2026, SODA 2026, STACS 2025, SeqBIM 2024, SPIRE 2024, IWOCA 2024, SeqBIM 2023, ESA 2023, MFCS 2021, ICALP 2020, SOSA 2020, CPM 2019, CPM 2018, CPM 2017, SPIRE 2017, IWOCA 2016, CSR 2016, SPIRE 2015, CPM 2015, CPM 2014.

I co-chaired CPM 2021 with P. Gawrychowski.

Selected publications

  1. Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms. with P. Charalampopoulos, T. El Ghazi, J. Ellert, P. Gawrychowski. (ICALP 2026): 55:1-55:20.
  2. Regular Languages in the Sliding Window Model. with M. Ganardi, D. Hucke, M. Lohrey, K. Mamouras. In TheoretiCS 4 (2025)
  3. Faster two-dimensional pattern matching with k mismatches. with J. Ellert, P. Gawrychowski, A. Górkiewicz. In the ACM-SIAM Symposium on Discrete Algorithms (SODA 2025): 4031-4060.
  4. An Improved Algorithm for The k-Dyck Edit Distance Problem. with D. Fried, S. Golan, T. Kociumaka, T. Kopelowitz, E. Porat. In ACM Trans. Algorithms 20(3): 26 (2024)
  5. Streaming Regular Expression Membership and Pattern Matching with B. Dudek, P. Gawrychowski, G. Gourdel. In the ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).
  6. 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).
  7. 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).
  8. 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).
  9. Improved bounds for testing Dyck languages with E. Fischer and F. Magniez, in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
  10. The k-mismatch problem revisited with R. Clifford, A. Fontaine, E. Porat, B. Sach, in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2016).