My research interests currently include:

• Probabilistic data structures, sketching
• Algorithms on words and trees, pattern matching, indexes for sequential data
• Combinatorial algorithms and their applications to computational molecular biology

Earlier research also covered abstract data type theory, automated deduction and term rewriting systems, and formal language theory.

For selected publications list, see Publications. For software I have contributed to, see the Software page. For a list of conferences and workshops I have attended, see the Conferences page.

Background and previous affiliations

My background is applied mathematics. I studied at the Institute of Electrical Engineering in Novosibirsk in Russia, now renamed to Novosibirsk State Technical University. Then I worked in what is now called the A.P.Ershov Institute of Informatics Systems in Novosibirsk Akademgorodok where I did my PhD in 1988 entitled Abstract data type specification and term rewriting systems (no pdf, sorry, it was typed on a typewriter machine!).

In 1991 I moved to the Loria lab in Nancy, France. In 1993 I joined INRIA where I worked until 2005. In 2005 I joined CNRS and moved to Lille, to the LIFL Lab (now part of CRIStAL lab). In 2008-2010, I made a two-years leave to the (now closed) French-Russian J.-V.Poncelet Lab in Moscow. From 2011, I am affiliated with the Laboratoire d’Informatique Gaspard-Monge at Marne-la-Vallée.

PhD Students Supervised

• Yoshihiro Shibuya (2018–2022)
• Kamil Salikhov (2013–2017, co-tutelle)
• Karel Brinda (2013–2016)
• Tatiana Starikovskaya (2009–2012, co-supervision)
• Marta Girdea (2007–2010, co-supervised)
• Ségolène Caboche (2006–2009, co-supervised)
• Fabrice Touzain (2003–2007, co-supervised)
• Laurent Noé (2002–2005)
• Vladimir Grebinski (1995–1998)