CSR 2011: St. Petersburg, Russia

• 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