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

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 -