Computer Science – Theory and Applications: 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013. Proceedings

Front Matter....Pages -
The Lovász Local Lemma – A Survey....Pages 1-11
An Improved Knapsack Solver for Column Generation....Pages 12-23
QuickHeapsort: Modifications and Improved Analysis....Pages 24-35
Alphabetic Minimax Trees in Linear Time....Pages 36-48
Decidability and Enumeration for Automatic Sequences: A Survey....Pages 49-63
Walking on Data Words....Pages 64-75
Careful Synchronization of Partial Automata with Restricted Alphabets....Pages 76-87
Random Generation of Deterministic Acyclic Automata Using the Recursive Method....Pages 88-99
Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height....Pages 100-111
A Short Tutorial on Order-Invariant First-Order Logic....Pages 112-126
Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams....Pages 127-138
Parameterized Resolution with Bounded Conjunction....Pages 139-149
Lower and Upper Bounds for the Length of Joins in the Lambek Calculus....Pages 150-161
Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP....Pages 162-173
Towards NEXP versus BPP?....Pages 174-182
Information Lower Bounds via Self-reducibility....Pages 183-194
On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles....Pages 195-202
Improving on Gutfreund, Shaltiel,and Ta-Shma’s Paper “If NP Languages Are Hard on the Worst-Case, Then It Is Easy to Find Their Hard Instances”....Pages 203-211
Amortized Communication Complexity of an Equality Predicate....Pages 212-223
On Coloring of Sparse Graphs....Pages 224-234
On Recognizing Words That Are Squares for the Shuffle Product....Pages 235-245
Cyclic Shift on Prefix-Free Languages....Pages 246-257
Weak Abelian Periodicity of Infinite Words....Pages 258-270
Universality of Regular Realizability Problems....Pages 271-282
Potential Functions in Strategic Games....Pages 283-297
The Probabilistic Min Dominating Set Problem....Pages 298-309
Dichotomy of the H -Quasi-Cover Problem....Pages 310-321
QCSP on Partially Reflexive Cycles – The Wavy Line of Tractability....Pages 322-333
Quantum Alternation....Pages 334-346
Real Numbers, Chaos, and the Principle of a Bounded Density of Information....Pages 347-353
Random Selection in Few Rounds....Pages 354-365
One-Counter Verifiers for Decidable Languages....Pages 366-377
More on the Complexity of Quantifier-Free Fixed-Size Bit-Vector Logics with Binary Encoding....Pages 378-390
Composition with Algebra at the Background....Pages 391-404
Model-Checking Bounded Multi-Pushdown Systems....Pages 405-417
Multi-weighted Automata and MSO Logic....Pages 418-430
Overlapping Tile Automata....Pages 431-443
Back Matter....Pages -