Computer Science – Theory and Applications: 14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019, Proceedings

Description

This book constitutes the proceedings of the 14th International Computer Science Symposium in Russia, CSR 2019, held in Novosibirsk, Russia, in July 2019. The 31 full papers were carefully reviewed and selected from 71 submissions. The papers cover a wide range of topics such as algorithms and data structures; computational complexity; randomness in computing; approximation algorithms; combinatorial optimization; constraint satisfaction; computational geometry; formal languages and automata; codes and cryptography; combinatorics in computer science; applications of logic to computer science; proof complexity; fundamentals of machine learning; and theoretical aspects of big data. Front Matter ....Pages i-xxv Approximability and Inapproximability for Maximum k-Edge-Colored Clustering Problem (Yousef M. Alhamdan, Alexander Kononov)....Pages 1-12 The Non-hardness of Approximating Circuit Size (Eric Allender, Rahul Ilango, Neekon Vafa)....Pages 13-24 Reconstructing a Convex Polygon from Its \(\omega \)-cloud (Elena Arseneva, Prosenjit Bose, Jean-Lou De Carufel, Sander Verdonschot)....Pages 25-37 A Space-Efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraization (Mahdi Belbasi, Martin Fürer)....Pages 38-49 Quantum Algorithm for Distribution-Free Junta Testing (Aleksandrs Belovs)....Pages 50-59 On Induced Online Ramsey Number of Paths, Cycles, and Trees (Václav Blažej, Pavel Dvořák, Tomáš Valla)....Pages 60-69 Approximations of Schatten Norms via Taylor Expansions (Vladimir Braverman)....Pages 70-79 Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes (Bireswar Das, Shivdutt Sharma)....Pages 80-92 Belga B-Trees (Erik D. Demaine, John Iacono, Grigorios Koumoutsos, Stefan Langerman)....Pages 93-105 Eventually Dendric Shifts (Francesco Dolce, Dominique Perrin)....Pages 106-118 On Decidability of Regular Languages Theories (Sergey Dudakov, Boris Karlov)....Pages 119-130 Minimizing Branching Vertices in Distance-Preserving Subgraphs (Kshitij Gajjar, Jaikumar Radhakrishnan)....Pages 131-142 On Tseitin Formulas, Read-Once Branching Programs and Treewidth (Ludmila Glinskih, Dmitry Itsykson)....Pages 143-155 Matched Instances of Quantum Satisfiability (QSat) – Product State Solutions of Restrictions (Andreas Goerdt)....Pages 156-167 Notes on Resolution over Linear Equations (Svyatoslav Gryaznov)....Pages 168-179 Undecidable Word Problem in Subshift Automorphism Groups (Pierre Guillon, Emmanuel Jeandel, Jarkko Kari, Pascal Vanier)....Pages 180-190 Parameterized Complexity of Conflict-Free Set Cover (Ashwin Jacob, Diptapriyo Majumdar, Venkatesh Raman)....Pages 191-202 Forward Looking Huffman Coding (Shmuel Tomi Klein, Shoham Saadia, Dana Shapira)....Pages 203-214 Computational Complexity of Real Powering and Improved Solving Linear Differential Equations (Ivan Koswara, Svetlana Selivanova, Martin Ziegler)....Pages 215-227 On the Quantum and Classical Complexity of Solving Subtraction Games (Dmitry Kravchenko, Kamil Khadiev, Danil Serov)....Pages 228-236 Derandomization for Sliding Window Algorithms with Strict Correctness (Moses Ganardi, Danny Hucke, Markus Lohrey)....Pages 237-249 On the Complexity of Restarting (Jan-Hendrik Lorenz)....Pages 250-261 On the Complexity of Mixed Dominating Set (Jayakrishnan Madathil, Fahad Panolan, Abhishek Sahu, Saket Saurabh)....Pages 262-274 Uniform CSP Parameterized by Solution Size is in W[1] (Ruhollah Majdoddin)....Pages 275-285 On the Parameterized Complexity of Edge-Linked Paths (Neeldhara Misra, Fahad Panolan, Saket Saurabh)....Pages 286-298 The Parameterized Complexity of Dominating Set and Friends Revisited for Structured Graphs (Neeldhara Misra, Piyush Rathi)....Pages 299-310 Transition Property for Cube-Free Words (Elena A. Petrova, Arseny M. Shur)....Pages 311-324 A Polynomial Time Delta-Decomposition Algorithm for Positive DNFs (Denis Ponomaryov)....Pages 325-336 Unpopularity Factor in the Marriage and Roommates Problems (Suthee Ruangwises, Toshiya Itoh)....Pages 337-348 AND Protocols Using only Uniform Shuffles (Suthee Ruangwises, Toshiya Itoh)....Pages 349-358 Sybil-Resilient Conductance-Based Community Growth (Ouri Poupko, Gal Shahaf, Ehud Shapiro, Nimrod Talmon)....Pages 359-371 Back Matter ....Pages 373-373