29 Jun-3 Jul 2020 Ekaterinburg (Russia)


CSR 2020 Schedule

Times slots are Ekaterinburg local time (summer CET +3)

IMPORTANT: all talks are pre-recorded and are available to all participants during the conference via playlists set up for each discussion session

Each live discussion session is intended for questions, answers, comments on the listed talks

Talks are also reachable via  Invited Speakers and Accepted Papers pages of this website 



Monday June 29th



Opening words

When is this in my timezone?


Business meeting, including the presentations of CSR 2021 and CSR 2022

 Here is the presentation of CSR 2021


Presentation of Best paper and Best student paper



Discussion session 1 (Best papers)

Chair: Mikhail Volkov


Fedor Fomin and Vijayaragunathan Ramamoorthi

On the Parameterized Complexity of the Expected Coverage Problem (Best paper)


Onur Çağırıcı

On embeddability of unit disk graphs onto straight lines (Best student paper)





Tuesday June 30th



Discussion session 2

Chair: Henning Fernau

When is this in my timezone?

Ulrik Brandes (invited lecture)

Central positions in social networks: concepts and some computational challenges


Tobias Rupp and Stefan Funke

A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels


Jasine Babu, Deepu Benson, Deepak Rajendraprasad and Sai Nishanth Vaka

An Improvement to Chvátal and Thomassen’s Upper Bound for Oriented Diameter


Discussion session 3

Chair: Arseny Shur

When is this in my timezone?

Geevarghese Philip, Rani M R and R. Subashini

On Computing the Hamiltonian Index of Graphs


Maxim Akhmedov

Faster 2-Disjoint-Shortest-Path Algorithm


Abhishek Sahu and Saket Saurabh

Kernelization of Arc Disjoint Cycle Packing in $\alpha$-bounded digraphs


Dmitry Kosolobov and Oleg Merkurev

Optimal Skeleton Huffman Trees Revisited


Discussion session 4

Chair: Eric Allender

When is this in my timezone?

Jaeyoon Kim, Ilya Volkovich and Nelson Xuzhi Zhang

The Power of Leibniz-Like Functions as Oracles


Ilya Volkovich

The Untold Story of SBP


Yaokun Wu and Yinfeng Zhu

Weighted rooted trees: Fat or tall?





Wednesday July 1st



Discussion session 5

Chair: Dominik Kempa

 When is this in my timezone?

Alexander Okhotin and Ilya Olkhovsky

On the transformation of LL(k)-linear grammars to LL(1)-linear


Iovka Boneva, Joachim Niehren and Momar Sakho

Nested Regular Expressions can be Compiled to Small Deterministic Nested Word Automata


Discussion session 6

Chair: Alexander Grigoriev

When is this in my timezone?

Mateus de Oliveira Oliveira (invited lecture)

Second-Order Finite Automata


Dietrich Kuske

The subtrace order and counting first-order logic


Nikolay Bazhenov

Definable subsets of polynomial-time algebraic structures


Akihiro Yamamura, Riki Kase and Tatiana Jajcayova

Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals





Thursday July 2nd



Discussion session 7

Chair: Jörg Rothe

When it this in my timezone?

Meirav Zehavi (invited lecture)

Parameterized Analysis of Art Gallery and Terrain Guarding


Lawqueen Kanesh, Soumen Maity, Komal Muluk and Saket Saurabh

Parameterized Complexity of Fair Feedback Vertex Set Problem


Bruno Bauwens and Ilya Blinnikov

The normalized algorithmic information distance can not be approximated


Discussion session 8

Chair: Meena Mahajan

When it this in my timezone?

Binhai Zhu (invited lecture)


Olivier Bodini, Antoine Genitrini, Mehdi Naima and Alexandros Singh

Tandem Duplications, Segmental Duplications and Deletions, and Their Applications


Families of Monotonic Trees: Combinatorial Enumeration and Asymptotics


Alexey Talambutsa

On subquadratic derivational complexity of semi-Thue systems


Anastasiya Chistopolskaya and Vladimir Podolskii

On the Decision Tree Complexity of Threshold Functions





Friday July 3rd



Discussion session 9

Chair: Andrei Krokhin

When is this in my timezone?

Farid Ablaev (invited lecture)

Quantum hashing and fingerprinting for quantum cryptography and computations


Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma and Raghunath Tewari

Randomized and Symmetric Catalytic Computation


Ivan Titov and Wolfgang Merkle

Speedable left-c.e. numbers.


Discussion session 10

Chair: Dmitry Kosolobov

When is this in my timezone?

Piotr Faliszewski (invited lecture)

Election Isomorphism Problem and Isomorphic Distances Among Elections


Marc Neveling, Jörg Rothe and Roman Zorn

The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters


Vladimir Gurvich and Mikhail Vyalyi

Computational Hardness of Multidimensional Subtraction Games





Online user: 10 Privacy