Computer Science – Theory and Applications

Description

This book constitutes the proceedings of the 13th International Computer Science Symposium in Russia, CSR 2018, held in Moscow, Russia, in May 2018. The 24 full papers presented together with 7 invited lectures were carefully reviewed and selected from 42 submissions. The papers cover a wide range of topics such as algorithms and data structures; combinatorial optimization; constraint solving; computational complexity; cryptography; combinatorics in computer science; formal languages and automata; algorithms for concurrent and distributed systems; networks; and proof theory and applications of logic to computer science. Front Matter ....Pages I-XXXII Complexity of Generation (Vladimir Gurvich)....Pages 1-14 Lower Bounds for Unrestricted Boolean Circuits: Open Problems (Alexander S. Kulikov)....Pages 15-22 Online Labeling: Algorithms, Lower Bounds and Open Questions (Michael Saks)....Pages 23-28 Maintaining Chordal Graphs Dynamically: Improved Upper and Lower Bounds (Niranka Banerjee, Venkatesh Raman, Srinivasa Rao Satti)....Pages 29-40 Distributed Symmetry-Breaking Algorithms for Congested Cliques (Leonid Barenboim, Victor Khazanov)....Pages 41-52 The Clever Shopper Problem (Laurent Bulteau, Danny Hermelin, Anthony Labarre, Stéphane Vialette)....Pages 53-64 A Tight Lower Bound for Steiner Orientation (Rajesh Chitnis, Andreas Emil Feldmann)....Pages 65-77 Can We Create Large k-Cores by Adding Few Edges? (Rajesh Chitnis, Nimrod Talmon)....Pages 78-89 Periodicity in Data Streams with Wildcards (Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou)....Pages 90-105 Maximum Colorful Cycles in Vertex-Colored Graphs (Giuseppe F. Italiano, Yannis Manoussakis, Nguyen Kim Thang, Hong Phong Pham)....Pages 106-117 Grammar-Based Compression of Unranked Trees (Adrià Gascón, Markus Lohrey, Sebastian Maneth, Carl Philipp Reh, Kurt Sieber)....Pages 118-131 Complement for Two-Way Alternating Automata (Viliam Geffert)....Pages 132-144 Closure Under Reversal of Languages over Infinite Alphabets (Daniel Genkin, Michael Kaminski, Liat Peterfreund)....Pages 145-156 Structural Parameterizations of Dominating Set Variants (Dishant Goyal, Ashwin Jacob, Kaushtubh Kumar, Diptapriyo Majumdar, Venkatesh Raman)....Pages 157-168 Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing (Sören Henning, Klaus Jansen, Malin Rau, Lars Schmarje)....Pages 169-180 Operations on Boolean and Alternating Finite Automata (Michal Hospodár, Galina Jirásková, Ivana Krajňáková)....Pages 181-193 Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized (Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra)....Pages 194-206 Quadratically Tight Relations for Randomized Query Complexity (Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal et al.)....Pages 207-219 On Vertex Coloring Without Monochromatic Triangles (Michał Karpiński, Krzysztof Piecuch)....Pages 220-231 Recognizing Read-Once Functions from Depth-Three Formulas (Alexander Kozachinskiy)....Pages 232-243 Max-Cut Above Spanning Tree is Fixed-Parameter Tractable (Jayakrishnan Madathil, Saket Saurabh, Meirav Zehavi)....Pages 244-256 Slopes of 3-Dimensional Subshifts of Finite Type (Etienne Moutot, Pascal Vanier)....Pages 257-268 Facility Location on Planar Graphs with Unreliable Links (N. S. Narayanaswamy, Meghana Nasre, R. Vijayaragunathan)....Pages 269-281 On the Decision Trees with Symmetries (Artur Riazanov)....Pages 282-294 On Emptiness and Membership Problems for Set Automata (A. Rubtsov, M. Vyalyi)....Pages 295-307 On Strong NP-Completeness of Rational Problems (Dominik Wojtczak)....Pages 308-320 A New Algorithm for Finding Closest Pair of Vectors (Extended Abstract) (Ning Xie, Shuai Xu, Yekun Xu)....Pages 321-333 Back Matter ....Pages 335-335