| 2009 | Variations on Muchnik's Conditional Complexity Theorem. | Daniil Musatov, Andrei Romashchenko, Alexander Shen |
| 2009 | The Budgeted Unique Coverage Problem and Color-Coding. | Neeldhara Misra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar |
| 2009 | Complete Complexity Classification of Short Shop Scheduling. | Alexander V. Kononov, Sergey Sevastyanov, Maxim Sviridenko |
| 2009 | Breaking Anonymity by Learning a Unique Minimum Hitting Set. | Dogan Kesdogan, Daniel Mlle, Stefan Richter, Peter Rossmanith |
| 2009 | Approximability of the Maximum Solution Problem for Certain Families of Algebras. | Peter Jonsson, Johan Thapper |
| 2009 | Concatenation of Regular Languages and Descriptional Complexity. | Galina Jirskov |
| 2009 | One-Nonterminal Conjunctive Grammars over a Unary Alphabet. | Artur Jez, Alexander Okhotin |
| 2009 | Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity. | Maurice J. Jansen, B. V. Raghavendra Rao |
| 2009 | Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials. | Maurice J. Jansen |
| 2009 | Structural Complexity of AvgBPP. | Dmitry Itsykson |
| 2009 | Partitioning Graphs into Connected Parts. | Pim van 't Hof, Danil Paulusma, Gerhard J. Woeginger |
| 2009 | A Feebly Secure Trapdoor Function. | Edward A. Hirsch, Sergey I. Nikolenko |
| 2009 | Formal Verification of Gate-Level Computer Systems. | Mark A. Hillebrand, Sergey Tverdyshev |
| 2009 | Compressed Word Problems in HNN-Extensions and Amalgamated Products. | Niko Haubold, Markus Lohrey |
| 2009 | Depth Reduction for Circuits with a Single Layer of Modular Counting Gates. | Kristoffer Arnsfelt Hansen |
| 2009 | On Random Ordering Constraints. | Andreas Goerdt |
| 2009 | Approximability Distance in the Space of | Tommy Frnqvist, Peter Jonsson, Johan Thapper |
| 2009 | Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model. | Yi Deng, Giovanni Di Crescenzo, Dongdai Lin, Dengguo Feng |
| 2009 | Unique Decipherability in the Monoid of Languages: An Application of Rational Relations. | Christian Choffrut, Juhani Karhumki |
| 2009 | Untitled record | Chris Calabro, Ramamohan Paturi |
| 2009 | Well-Founded and Partial Stable Semantics Logical Aspects. | Pedro Cabalar, Sergei P. Odintsov, David Pearce |
| 2009 | Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes. | Olaf Beyersdorff, Zenon Sadowski |
| 2009 | Integrality Property in Preemptive Parallel Machine Scheduling. | Philippe Baptiste, Jacques Carlier, Alexander V. Kononov, Maurice Queyranne, Sergey Sevastyanov, Maxim Sviridenko |
| 2009 | Canonical Calculi: Invertibility, Axiom Expansion and (Non)-determinism. | Arnon Avron, Agata Ciabattoni, Anna Zamansky |
| 2008 | Simple Stochastic Games, Mean Payoff Games, Parity Games. | Uri Zwick |