CSR 2011:
St. Petersburg,
Russia
Alexander S. Kulikov, Nikolay K. Vereshchagin (Eds.):
Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings.
Lecture Notes in Computer Science 6651 Springer 2011, ISBN 978-3-642-20711-2
- Scott Aaronson:
The Equivalence of Sampling and Searching.
1-14
- Benjamin Doerr, Carola Winzen:
Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity.
15-28
- Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien:
Learning Read-Constant Polynomials of Constant Degree Modulo Composites.
29-42
- Manindra Agrawal:
On the Arithmetic Complexity of Euler Function.
43-49
- Andrei E. Romashchenko:
Pseudo-random Graphs and Bit Probe Schemes with One-Sided Error.
50-63
- Daniil Musatov:
Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization.
64-76
- Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen:
The Complexity of Solving Reachability Games Using Value and Strategy Iteration.
77-90
- Alexey Pospelov:
Faster Polynomial Multiplication via Discrete Fourier Transforms.
91-104
- Alexander Shen:
Kolmogorov Complexity as a Language.
105-119
- Jirí Síma, Stanislav Zák:
Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs.
120-133
- Dmitry Itsykson, Dmitry Sokolov:
The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms.
134-147
- Alex Davydow, Sergey I. Nikolenko:
Gate Elimination for Linear Functions and New Feebly Secure Constructions.
148-161
- László Babai:
Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas.
162-180
- Catarina Carvalho, László Egri, Marcel Jackson, Todd Niven:
On Maltsev Digraphs.
181-194
- Loukas Georgiadis, Stavros D. Nikolopoulos, Leonidas Palios:
Join-Reachability Problems in Directed Graphs.
195-208
- Fabian Wagner:
Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$\mbox{{\sf AC}.
209-222
- Jarkko Kari:
Snakes and Cellular Automata: Reductions and Inseparability Results.
223-232
- Pinar Heggernes, Daniel Meister, Udi Rotics:
Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width.
233-246
- Klaus Meer:
An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents.
247-260
- Petr A. Golovach, Daniël Paulusma, Jian Song:
Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees.
261-274
- Markus Lohrey, Christian Mathissen:
Compressed Membership in Automata with Compressed Labels.
275-288
- Sergey Yekhanin:
Locally Decodable Codes.
289-290
- Violetta Lonati, Dino Mandrioli, Matteo Pradella:
Precedence Automata and Languages.
291-304
- Sergey P. Tarasov, Mikhail N. Vyalyi:
Orbits of Linear Maps and Regular Languages.
305-316
- Rémi Morin:
Shared-Memory Systems and Charts.
317-330
- Andrei A. Bulatov:
On the CSP Dichotomy Conjecture.
331-344
- Tamar Aizikowitz, Michael Kaminski:
LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata.
345-358
- Christos A. Kapoutsis:
Two-Way Automata versus Logarithmic Space.
359-372
- Guillaume Blin, Romeo Rizzi, Stéphane Vialette:
A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row.
373-384
- Konstantin M. Likhomanov, Arseny M. Shur:
Two Combinatorial Criteria for BWT Images.
385-396
- Amir Shpilka:
Recent Results on Polynomial Identity Testing.
397-400
- Alexander Tiskin:
Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition.
401-414
- Eric Rémila:
The Optimal Strategy for the Average Long-Lived Consensus.
415-428
- Nguyen Kim Thang:
Improved Online Scheduling in Maximizing Throughput of Equal Length Jobs.
429-442
- Matthijs Bomhoff:
Recognizing Sparse Perfect Elimination Bipartite Graphs.
443-455
- Arnon Avron, Ori Lahav:
A Multiple-Conclusion Calculus for First-Order Gödel Logic.
456-469
Last update Thu May 24 04:15:35 2012
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page