29 Jun-3 Jul 2020 Ekaterinburg (Russia)

Schedule

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

 

18:00--18:05

Opening words

When is this in my timezone?

18:05--18:30

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

 Here is the presentation of CSR 2021

18:30--18:40

Presentation of Best paper and Best student paper

 

18:40--19:00

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

 

13:30--14:00

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

16:00--16:30

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

19:00--19:30

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

 

13:30--14:00

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

16:00--16:30

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

 

16:00--17:00

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

19:00--20:00

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

 

13:30--14:30

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.

16:00--17:00

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

 

 

 

 

e
Online user: 1