29 Jun-3 Jul 2020 Ekaterinburg (Russia)

Accepted Papers

Links to all video presentations have been added.  They are also available via the playlist CSR 2020: Contributed talks

Abhishek Sahu and Saket Saurabh. Kernelization of Arc Disjoint Cycle Packing in $\alpha$-bounded digraphs

Akihiro Yamamura, Riki Kase and Tatiana Jajcayova. Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals

Alexander Okhotin and Ilya Olkhovsky. On the transformation of LL(k)-linear grammars to LL(1)-linear

Alexey Talambutsa. On subquadratic derivational complexity of semi-Thue systems

Anastasiya Chistopolskaya and Vladimir Podolskii. On the Decision Tree Complexity of Threshold Functions

Bruno Bauwens and Ilya Blinnikov.  The normalized algorithmic information distance can not be approximated

Dietrich Kuske. The subtrace order and counting first-order logic;  Additional materials are provided here

Dmitry Kosolobov and Oleg Merkurev.  Optimal Skeleton Huffman Trees Revisited

Fedor Fomin and Vijayaragunathan Ramamoorthi. On the Parameterized Complexity of the Expected Coverage Problem

Geevarghese Philip, Rani M R and R. Subashini. On Computing the Hamiltonian Index of Graphs

Ilya Volkovich. The Untold Story of SBP

Iovka Boneva, Joachim Niehren and Momar Sakho. Nested Regular Expressions can be Compiled to Small Deterministic Nested Word Automata

Ivan Titov and Wolfgang Merkle. Speedable left-c.e. numbers

Jaeyoon Kim, Ilya Volkovich and Nelson Xuzhi Zhang. The Power of Leibniz-Like Functions as Oracles

Jasine Babu, Deepu Benson, Deepak Rajendraprasad and Sai Nishanth Vaka. An Improvement to Chvátal and Thomassen’s Upper Bound for Oriented Diameter

Lawqueen Kanesh, Soumen Maity, Komal Muluk and Saket Saurabh. Parameterized Complexity of Fair Feedback Vertex Set Problem

Marc Neveling, Jörg Rothe and Roman Zorn. The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters

Maxim Akhmedov. Faster 2-Disjoint-Shortest-Path Algorithm

Nikolay Bazhenov. Definable subsets of polynomial-time algebraic structures

Olivier Bodini, Antoine Genitrini, Mehdi Naima and Alexandros Singh. Families of Monotonic Trees: Combinatorial Enumeration and Asymptotics

Onur Çağırıcı. On embeddability of unit disk graphs onto straight lines

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma and Raghunath Tewari. Randomized and Symmetric Catalytic Computation

Tobias Rupp and Stefan Funke. A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels

Vladimir Gurvich and Mikhail Vyalyi. Computational Hardness of Multidimensional Subtraction Games

Yaokun Wu and Yinfeng Zhu. Weighted rooted trees: Fat or tall?



Online user: 1