Computer Science - Theory and Applications: 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings

by Pascal Weil (Editor)

Type Theory and Formalization of Mathematics.- Advances in Parameterized Verification of Population Protocols.- Verification of Quantum Computation and the Price of Trust.- Graph Sketching and New Approaches for Analyzing Massive Graphs.- Concatenation New Bottle, Old Wine.- Can We Locally Compute Sparse Connected Subgraphs.- Palindromic Decompositions with Gaps and Errors.- Cascade Towards Time-Optimal Extractions.- Entropic Uniform Sampling of Linear Extensions in Series-Parallel Posets.- Parameterized Counting of Trees, Forests and Matroid Bases.- Generalized Dyck Shifts.- Green's Relations in Finite Transformation Semigroups.- Nondeterministic Unitary OBDDs.- Unary Coded PSPACE-Complete Languages in ASPACE(loglog n).- Turing Degree Spectra of Minimal Subshifts.- Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams.- Dynamic stabbing Queries with Sub-logarithmic Local Updates for Overlapping Intervals.- The Transformation Monoid of a Partially Lossy Queue.- Approximation Algorithms for the Maximum Carpool Matching Problem.- The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC=0.- On Algorithmic Statistics for Space-bounded Algorithms.- Popularity in the Generalized Hospital Residents Setting.- Edit Distance Neighbourhoods of Input-driven Pushdown Automata.- The (Minimum) Rank of Typical Fooling-set Matrices.- On Probabilistic Algorithm for Solving Almost All Instances of the Set Partition Problem.- Dag-like Communication and Its Applications.- The Descriptive Complexity of Subgraph Isomorphism Without Numerics.- On a Generalization of Horn Constraint Systems. 

348 pages, Paperback

Published May 12, 2017