Computer Science - Theory and Applications 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings

Finding All Solutions of Equations in Free Groups and Monoids with Involution.- Algorithmic Meta Theorems for Sparse Graph Classes.- The Lattice of Definability.- Counting Popular Matchings in House Allocation Problems.- Vertex Disjoint Paths in Upward Planar Graphs.- On Lower Bounds for Multiplicative Circuits and Linear Circuits in Noncommutative Domains.- Testing low degree trigonometric polynomials.- Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees.- A Fast Branching Algorithm for Cluster Vertex Deletion.- Separation Logic with One Quantified Variable.- Notions of metric dimension of corona products.- On the Complexity of Computing Two Nonlinearity Measures.- Model Checking for String Problems.- Semiautomatic Structures.- The Query Complexity of Witness Finding.- Primal implication as encryption.- Processing Succinct Matrices and Vectors.- Constraint Satisfaction with Counting Quantifiers.- Dynamic Complexity of Planar 3-connected Graph Isomorphism.- Fast Approximate Computations with Cauchy Matrices, Polynomials and Rational Functions.- First-Order Logic on CPDA Graphs.- Recognizing two-sided contexts in cubic time.- A Parameterized Algorithm for Packing Overlapping Subgraphs.- Crossing-free spanning trees in visibility graphs of points between monotone polygonal obstacles.- The Connectivity of Boolean Satisfiability.- Randomized communication complexity of approximating Kolmogorov complexity.- Space Saving by Dynamic Algebraization.