Computer Science – Theory and Applications: 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings

Front Matter ....Pages i-xi
 Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations  (Farid Ablayev, Marat Ablayev, Alexander Vasiliev)....Pages 1-15
 Parameterized Analysis of Art Gallery and Terrain Guarding  (Akanksha Agrawal, Meirav Zehavi)....Pages 16-29
 Central Positions in Social Networks  (Ulrik Brandes)....Pages 30-45
 Second-Order Finite Automata  (Alexsander Andrade de Melo, Mateus de Oliveira Oliveira)....Pages 46-63
 Isomorphic Distances Among Elections  (Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Stanisław Szufa, Nimrod Talmon)....Pages 64-78
 Tandem Duplications, Segmental Duplications and Deletions, and Their Applications  (Binhai Zhu)....Pages 79-102
 Faster 2-Disjoint-Shortest-Paths Algorithm  (Maxim Akhmedov)....Pages 103-116
 An Improvement to Chvátal and Thomassen’s Upper Bound for Oriented Diameter  (Jasine Babu, Deepu Benson, Deepak Rajendraprasad, Sai Nishant Vaka)....Pages 117-129
 The Normalized Algorithmic Information Distance Can Not Be Approximated  (Bruno Bauwens, Ilya Blinnikov)....Pages 130-141
 Definable Subsets of Polynomial-Time Algebraic Structures  (Nikolay Bazhenov)....Pages 142-154
 Families of Monotonic Trees: Combinatorial Enumeration and Asymptotics  (Olivier Bodini, Antoine Genitrini, Mehdi Naima, Alexandros Singh)....Pages 155-168
 Nested Regular Expressions Can Be Compiled to Small Deterministic Nested Word Automata  (Iovka Boneva, Joachim Niehren, Momar Sakho)....Pages 169-183
 On Embeddability of Unit Disk Graphs onto Straight Lines  (Onur Çağırıcı)....Pages 184-197
 On the Decision Tree Complexity of Threshold Functions  (Anastasiya Chistopolskaya, Vladimir V. Podolskii)....Pages 198-210
 Randomized and Symmetric Catalytic Computation  (Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari)....Pages 211-223
 On the Parameterized Complexity of the Expected Coverage Problem  (Fedor V. Fomin, Vijayaragunathan Ramamoorthi)....Pages 224-236
 Computational Hardness of Multidimensional Subtraction Games  (Vladimir Gurvich, Mikhail Vyalyi)....Pages 237-249
 Parameterized Complexity of Fair Feedback Vertex Set Problem  (Lawqueen Kanesh, Soumen Maity, Komal Muluk, Saket Saurabh)....Pages 250-262
 The Power of Leibniz-Like Functions as Oracles  (Jaeyoon Kim, Ilya Volkovich, Nelson Xuzhi Zhang)....Pages 263-275
 Optimal Skeleton Huffman Trees Revisited  (Dmitry Kosolobov, Oleg Merkurev)....Pages 276-288
 The Subtrace Order and Counting First-Order Logic  (Dietrich Kuske)....Pages 289-302
 Speedable Left-c.e. Numbers  (Wolfgang Merkle, Ivan Titov)....Pages 303-313
 The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters  (Marc Neveling, Jörg Rothe, Roman Zorn)....Pages 314-327
 On the Transformation of LL(k)-linear Grammars to LL(1)-linear  (Alexander Okhotin, Ilya Olkhovsky)....Pages 328-340
 On Computing the Hamiltonian Index of Graphs  (Geevarghese Philip, M. R. Rani, R. Subashini)....Pages 341-353
 A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels  (Tobias Rupp, Stefan Funke)....Pages 354-366
 Kernelization of Arc Disjoint Cycle Packing in \(\alpha \)-Bounded Digraphs  (Abhishek Sahu, Saket Saurabh)....Pages 367-378
 On Subquadratic Derivational Complexity of Semi-Thue Systems  (Alexey Talambutsa)....Pages 379-392
 The Untold Story of \(\mathsf {SBP}\)  (Ilya Volkovich)....Pages 393-405
 Weighted Rooted Trees: Fat or Tall?  (Yaokun Wu, Yinfeng Zhu)....Pages 406-418
 Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals  (Akihiro Yamamura, Riki Kase, Tatiana B. Jajcayová)....Pages 419-431
Back Matter ....Pages 433-433