Computer Science – Theory and Applications : 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings

Annotation This book constitutes the proceedings of the 6th International Computer Science Symposium in Russia, CSR 2011, held in St. Petersburg, Russia, in June 2011. The 29 papers presented were carefully reviewed and selected from 76 submissions. The scope of topics of the symposium was quite broad and covered basically all areas of the foundations of theoretical computer science Front Matter....Pages - The Equivalence of Sampling and Searching....Pages 1-14 Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity....Pages 15-28 Learning Read-Constant Polynomials of Constant Degree Modulo Composites....Pages 29-42 On the Arithmetic Complexity of Euler Function....Pages 43-49 Pseudo-random Graphs and Bit Probe Schemes with One-Sided Error....Pages 50-63 Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization....Pages 64-76 The Complexity of Solving Reachability Games Using Value and Strategy Iteration....Pages 77-90 Faster Polynomial Multiplication via Discrete Fourier Transforms....Pages 91-104 Kolmogorov Complexity as a Language....Pages 105-119 Almost k -Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs....Pages 120-133 The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms....Pages 134-147 Gate Elimination for Linear Functions and New Feebly Secure Constructions....Pages 148-161 Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas....Pages 162-180 On Maltsev Digraphs....Pages 181-194 Join-Reachability Problems in Directed Graphs....Pages 195-208 Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$ ....Pages 209-222 Snakes and Cellular Automata: Reductions and Inseparability Results....Pages 223-232 Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width....Pages 233-246 An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents....Pages 247-260 Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees....Pages 261-274 Compressed Membership in Automata with Compressed Labels....Pages 275-288 Locally Decodable Codes....Pages 289-290 Precedence Automata and Languages....Pages 291-304 Orbits of Linear Maps and Regular Languages....Pages 305-316 Shared-Memory Systems and Charts....Pages 317-330 On the CSP Dichotomy Conjecture....Pages 331-344 LR (0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata....Pages 345-358 Two-Way Automata versus Logarithmic Space....Pages 359-372 A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row....Pages 373-384 Two Combinatorial Criteria for BWT Images....Pages 385-396 Recent Results on Polynomial Identity Testing....Pages 397-400 Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition....Pages 401-414 The Optimal Strategy for the Average Long-Lived Consensus....Pages 415-428 Improved Online Scheduling in Maximizing Throughput of Equal Length Jobs....Pages 429-442 Recognizing Sparse Perfect Elimination Bipartite Graphs....Pages 443-455 A Multiple-Conclusion Calculus for First-Order Gödel Logic....Pages 456-469 Back Matter....Pages -