Computer Science - Theory and Applications

1. Front Matter

   PDF

2. Finding All Solutions of Equations in Free Groups and Monoids with Involution

   • Volker Diekert, Artur Jeż, Wojciech Plandowski

   Pages 1-15

3. Algorithmic Meta Theorems for Sparse Graph Classes

   • Martin Grohe

   Pages 16-22

4. The Lattice of Definability. Origins, Recent Developments, and Further Directions

   • Alexei Semenov, Sergey Soprunov, Vladimir Uspensky

   Pages 23-38

5. Counting Popular Matchings in House Allocation Problems

   • Rupam Acharyya, Sourav Chakraborty, Nitesh Jha

   Pages 39-51

6. Vertex Disjoint Paths in Upward Planar Graphs

   • Saeed Akhoondian Amiri, Ali Golshani, Stephan Kreutzer, Sebastian Siebertz

   Pages 52-64

7. On Lower Bounds for Multiplicative Circuits and Linear Circuits in Noncommutative Domains

   • V. Arvind, S. Raja, A. V. Sreejith

   Pages 65-76

8. Testing Low Degree Trigonometric Polynomials

   • Martijn Baartse, Klaus Meer

   Pages 77-96

9. Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees

   • Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni

   Pages 97-110

10. A Fast Branching Algorithm for Cluster Vertex Deletion

    • Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk

    Pages 111-124

11. Separation Logic with One Quantified Variable

    • Stéphane Demri, Didier Galmiche, Dominique Larchey-Wendling, Daniel Méry

    Pages 125-138

12. QuickXsort: Efficient Sorting with n logn − 1.399n + o(n) Comparisons on Average

    • Stefan Edelkamp, Armin Weiß

    Pages 139-152

13. Notions of Metric Dimension of Corona Products: Combinatorial and Computational Results

    • Henning Fernau, Juan Alberto Rodríguez-Velázquez

    Pages 153-166

14. On the Complexity of Computing Two Nonlinearity Measures

    • Magnus Gausdal Find

    Pages 167-175

15. Block Products and Nesting Negations in FO2

    • Lukas Fleischer, Manfred Kufleitner, Alexander Lauser

    Pages 176-189

16. Model Checking for String Problems

    • Milka Hutagalung, Martin Lange

    Pages 190-203

17. Semiautomatic Structures

    • Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan, Dan Teng, Siyuan Zou

    Pages 204-217

18. The Query Complexity of Witness Finding

    • Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

    Pages 218-231

19. Primal Implication as Encryption

    • Vladimir N. Krupski

    Pages 232-244

20. Processing Succinct Matrices and Vectors

    • Markus Lohrey, Manfred Schmidt-Schauß

    Pages 245-258

This book constitutes the proceedings of the 9th International Computer Science Symposium in Russia, CSR 2014, held in Moscow, Russia, in June 2014. The 27 full papers presented in this volume were carefully reviewed and selected from 76 submissions. In addition the book contains 4 invited lectures. The scope of the proposed topics is quite broad and covers a wide range of areas in theoretical computer science and its applications.

• approximation algorithms
• computational complexity
• discrete mathematics
• graph algorithms
• graph theory
• mathematical analysis
• numerical analysis
• theoretical computer science
• theory of computation
• algorithm analysis and problem complexity

• Steklov Institute of Mathematics at St. Petersburg, Russian Academy of Sciences, St. Petersburg, Russia

  Edward A. Hirsch

• Higher School of Economics, National Research University, Moscow, Russia

  Sergei O. Kuznetsov

• CNRS and University Paris Diderot, Paris, France

  Jean-Éric Pin

• Moscow State University, Moscow, Russia

  Nikolay K. Vereshchagin

Policies and ethics