Computer Science - Theory and Applications

1. Front Matter

   PDF

2. Opening Lecture

   1. The Lovász Local Lemma – A Survey

      • Mario Szegedy

      Pages 1-11

3. Session 1: Algorithms

   1. An Improved Knapsack Solver for Column Generation

      • Klaus Jansen, Stefan Kraft

      Pages 12-23

   2. QuickHeapsort: Modifications and Improved Analysis

      • Volker Diekert, Armin Weiß

      Pages 24-35

   3. Alphabetic Minimax Trees in Linear Time

      • Paweł Gawrychowski

      Pages 36-48

4. Invited Lecture 1

   1. Decidability and Enumeration for Automatic Sequences: A Survey

      • Jeffrey Shallit

      Pages 49-63

5. Session 2: Automata

   1. Walking on Data Words

      • Amaldev Manuel, Anca Muscholl, Gabriele Puppis

      Pages 64-75

   2. Careful Synchronization of Partial Automata with Restricted Alphabets

      • Pavel V. Martyugin

      Pages 76-87

   3. Random Generation of Deterministic Acyclic Automata Using the Recursive Method

      • Sven De Felice, Cyril Nicaud

      Pages 88-99

   4. Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height

      • Viliam Geffert, Zuzana Bednárová, Carlo Mereghetti, Beatrice Palano

      Pages 100-111

6. Invited Lecture 2

   1. A Short Tutorial on Order-Invariant First-Order Logic

      • Nicole Schweikardt

      Pages 112-126

7. Session 3: Logic, Proof Complexity

   1. Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams

      • Luke Friedman, Yixin Xu

      Pages 127-138

   2. Parameterized Resolution with Bounded Conjunction

      • Stefan Dantchev, Barnaby Martin

      Pages 139-149

   3. Lower and Upper Bounds for the Length of Joins in the Lambek Calculus

      • Alexey Sorokin

      Pages 150-161

   4. Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP

      • Dmitry Itsykson, Vsevolod Oparin

      Pages 162-173

8. Invited Lecture 3

   1. Towards NEXP versus BPP?

      • Ryan Williams

      Pages 174-182

9. Session 4: Complexity 1

   1. Information Lower Bounds via Self-reducibility

      • Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

      Pages 183-194

   2. On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles

      • Anton Makhlin

      Pages 195-202

   3. 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”

      • Nikolay Vereshchagin

      Pages 203-211

   4. Amortized Communication Complexity of an Equality Predicate

      • Vladimir Nikishkin

      Pages 212-223

This book constitutes the proceedings of the 8th International Computer Science Symposium in Russia, CSR 2013, held in Ekaterinburg, Russia, in June 2013. The 29 full papers presented in this volume were carefully reviewed and selected from 52 submissions. In addition the book contains 8 invited lectures. The papers are organized in topical sections on: algorithms; automata; logic and proof complexity; complexity; words and languages; and logic and automata.

• computational complexity
• decidability
• formal methods
• multi-weighted automata
• prefix-free languages
• algorithm analysis and problem complexity

• School of Computing Science, Simon Fraser University, Burnaby, Canada

  Andrei A. Bulatov

• Institute of Mathematics and Computer Science, Ural Federal University, Ekaterinburg, Russia

  Arseny M. Shur

Policies and ethics