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

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

  1. 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).
  2. Streaming Regular Expression Membership and Pattern Matching with B. Dudek, P. Gawrychowski, G. Gourdel. In the ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).
  3. 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).
  4. 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).
  5. 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).
  6. Improved bounds for testing Dyck languages with E. Fischer and F. Magniez, in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
  7. The k-mismatch problem revisited with R. Clifford, A. Fontaine, E. Porat, B. Sach, in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2016).
  8. Wavelet Trees Meet Suffix Trees with M. Babenko, P. Gawrychowski, T. Kociumaka, in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).