default search action
CSR 2013: Ekaterinburg, Russia
- Andrei A. Bulatov, Arseny M. Shur:
Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013. Proceedings. Lecture Notes in Computer Science 7913, Springer 2013, ISBN 978-3-642-38535-3
Opening Lecture
- Mario Szegedy:
The Lovász Local Lemma - A Survey. 1-11
Session 1: Algorithms
- Klaus Jansen, Stefan Erich Julius Kraft:
An Improved Knapsack Solver for Column Generation. 12-23 - Volker Diekert, Armin Weiß
:
QuickHeapsort: Modifications and Improved Analysis. 24-35 - Pawel Gawrychowski:
Alphabetic Minimax Trees in Linear Time. 36-48
Invited Lecture 1
- Jeffrey O. Shallit:
Decidability and Enumeration for Automatic Sequences: A Survey. 49-63
Session 2: Automata
- Amaldev Manuel, Anca Muscholl, Gabriele Puppis:
Walking on Data Words. 64-75 - Pavel V. Martyugin:
Careful Synchronization of Partial Automata with Restricted Alphabets. 76-87 - Sven De Felice, Cyril Nicaud:
Random Generation of Deterministic Acyclic Automata Using the Recursive Method. 88-99 - Viliam Geffert, Zuzana Bednárová, Carlo Mereghetti, Beatrice Palano:
Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height. 100-111
Invited Lecture 2
- Nicole Schweikardt:
A Short Tutorial on Order-Invariant First-Order Logic. 112-126
Session 3: Logic, Proof Complexity
- Luke Friedman, Yixin Xu:
Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams. 127-138 - Stefan S. Dantchev, Barnaby Martin:
Parameterized Resolution with Bounded Conjunction. 139-149 - Alexey Sorokin:
Lower and Upper Bounds for the Length of Joins in the Lambek Calculus. 150-161 - Dmitry Itsykson, Vsevolod Oparin:
Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP. 162-173
Invited Lecture 3
- Ryan Williams:
Towards NEXP versus BPP? 174-182
Session 4: Complexity 1
- Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
Information Lower Bounds via Self-reducibility. 183-194 - Anton Makhlin:
On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles. 195-202 - Nikolay K. Vereshchagin:
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". 203-211 - Vladimir Nikishkin
Amortized Communication Complexity of an Equality Predicate. 212-223
Invited Lecture 4
- Alexandr V. Kostochka, Matthew P. Yancey:
On Coloring of Sparse Graphs. 224-234
Session 5: Words and Languages
- Romeo Rizzi, Stéphane Vialette:
On Recognizing Words That Are Squares for the Shuffle Product. 235-245 - Jozef Jirásek, Galina Jirásková:
Cyclic Shift on Prefix-Free Languages. 246-257 - Sergey V. Avgustinovich, Svetlana Puzynina:
Weak Abelian Periodicity of Infinite Words. 258-270 - Mikhail N. Vyalyi:
Universality of Regular Realizability Problems. 271-282
Invited Lecture 5
- Paul G. Spirakis, Panagiota N. Panagopoulou:
Potential Functions in Strategic Games. 283-297
Session 6: Algorithms 2
- Nicolas Boria, Cécile Murat, Vangelis Th. Paschos:
The Probabilistic Min Dominating Set Problem. 298-309 - Jirí Fiala, Marek Tesar:
Dichotomy of the H-Quasi-Cover Problem. 310-321 - Florent R. Madelaine
QCSP on Partially Reflexive Cycles - The Wavy Line of Tractability. 322-333 - Abuzer Yakaryilmaz:
Quantum Alternation. 334-346
Invited Lecture 6
- Gilles Dowek:
Real Numbers, Chaos, and the Principle of a Bounded Density of Information. 347-353
Session 7: Complexity 2
- Timofey Stepanov:
Random Selection in Few Rounds. 354-365 - Abuzer Yakaryilmaz:
One-Counter Verifiers for Decidable Languages. 366-377 - Andreas Fröhlich, Gergely Kovásznai, Armin Biere:
More on the Complexity of Quantifier-Free Fixed-Size Bit-Vector Logics with Binary Encoding. 378-390
Invited Lecture 7
- Thomas Colcombet:
Composition with Algebra at the Background - On a Question by Gurevich and Rabinovich on the Monadic Theory of Linear Orderings. 391-404
Session 8: Logic, Automata
- Kshitij Bansal, Stéphane Demri:
Model-Checking Bounded Multi-Pushdown Systems. 405-417 - Manfred Droste, Vitaly Perevoshchikov:
Multi-weighted Automata and MSO Logic. 418-430 - David Janin:
Overlapping Tile Automata. 431-443
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-13 19:16 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: