| 2011 | Pseudo-random Graphs and Bit Probe Schemes with One-Sided Error. | Andrei Romashchenko |
| 2011 | The Optimal Strategy for the Average Long-Lived Consensus. | Eric Rmila |
| 2011 | Faster Polynomial Multiplication via Discrete Fourier Transforms. | Alexey Pospelov |
| 2011 | Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization. | Daniil Musatov |
| 2011 | Shared-Memory Systems and Charts. | Rmi Morin |
| 2011 | An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents. | Klaus Meer |
| 2011 | Precedence Automata and Languages. | Violetta Lonati, Dino Mandrioli, Matteo Pradella |
| 2011 | Compressed Membership in Automata with Compressed Labels. | Markus Lohrey, Christian Mathissen |
| 2011 | Two Combinatorial Criteria for BWT Images. | Konstantin M. Likhomanov, Arseny M. Shur |
| 2011 | Snakes and Cellular Automata: Reductions and Inseparability Results. | Jarkko Kari |
| 2011 | Two-Way Automata versus Logarithmic Space. | Christos A. Kapoutsis |
| 2011 | The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms. | Dmitry Itsykson, Dmitry Sokolov |
| 2011 | Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width. | Pinar Heggernes, Daniel Meister, Udi Rotics |
| 2011 | The Complexity of Solving Reachability Games Using Value and Strategy Iteration. | Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen |
| 2011 | Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees. | Petr A. Golovach, Danil Paulusma, Jian Song |
| 2011 | Join-Reachability Problems in Directed Graphs. | Loukas Georgiadis, Stavros D. Nikolopoulos, Leonidas Palios |
| 2011 | Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity. | Benjamin Doerr, Carola Winzen |
| 2011 | Gate Elimination for Linear Functions and New Feebly Secure Constructions. | Alex Davydow, Sergey I. Nikolenko |
| 2011 | Learning Read-Constant Polynomials of Constant Degree Modulo Composites. | Arkadev Chattopadhyay, Ricard Gavald, Kristoffer Arnsfelt Hansen, Denis Thrien |
| 2011 | On Maltsev Digraphs. | Catarina Carvalho, Lszl Egri, Marcel Jackson, Todd Niven |
| 2011 | On the CSP Dichotomy Conjecture. | Andrei A. Bulatov |
| 2011 | Recognizing Sparse Perfect Elimination Bipartite Graphs. | Matthijs Bomhoff |
| 2011 | A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row. | Guillaume Blin, Romeo Rizzi, Stphane Vialette |
| 2011 | Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas. | Lszl Babai |
| 2011 | A Multiple-Conclusion Calculus for First-Order Gdel Logic. | Arnon Avron, Ori Lahav |