Computer Science - Theory and Applications: 14th International Computer Science Symposium in Russia, Csr 2019, Novosibirsk, Russia, July 1-5, 2019, Pr

ISBN-13: 9783030199548 / Angielski / Miękka / 2019 / 373 str.

Rene Van Bevern; Gregory Kucherov

Spis treści

Approximability and Inapproximability for Maximum k-Edge-Colored Clustering Problem.- The Non-Hardness of Approximating Circuit Size.- Reconstructing a convex polygon from its omega-cloud.- A Space-efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraization.- Quantum Algorithm for Distribution-Free Junta Testing.- On Induced Online Ramsey Number of Paths, Cycles, and Trees.- Approximations of Schatten Norms via Taylor Expansions.- Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes.- Belga B-trees.- Eventually dendric shifts.- On Decidability of Regular Languages Theories.- Minimizing Branching Vertices in Distance-preserving Subgraphs.- On Tseitin formulas, read-once branching programs and treewidth.- Matched instances of Quantum Sat (QSat) - Product state solutions of Restrictions.- Notes on resolution over linear equations.- Undecidable word problem in subshift automorphism groups.- Parameterized Complexity of Conflict-Free Set Cover.- Forward Looking Huffman Coding.- Computational Complexity of Real Powering and Improved Solving Linear Differential Equations.- On the Quantum and Classical Complexity of Solving Subtraction Games.- Derandomization for sliding window algorithms with strict correctness.- On the Complexity of Restarting.- On the Complexity of Mixed Dominating Set.- Uniform CSP Parameterized by Solution Size is in W[1].- On the Parameterized Complexity of Edge-Linked Paths.- The Parameterized Complexity of Dominating Set and Friends Revisited.- Transition property for cube-free words.- A Polynomial Time Delta-Decomposition Algorithm for Positive DNFs.- Unpopularity Factor in the Marriage and Roommates Problems.- AND Protocols Using Only Uniform Shuffles.- Sybil-Resilient Conductance-Based Community Expansion.