| 2010 | Compositional Closure for Bayes Risk in Probabilistic Noninterference. | Annabelle McIver, Larissa Meinicke, Carroll Morgan |
| 2010 | B and D Are Enough to Make the Halpern-Shoham Logic Undecidable. | Jerzy Marcinkowski, Jakub Michaliszyn, Emanuel Kieronski |
| 2010 | Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm. | Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko |
| 2010 | Clustering with Diversity. | Jian Li, Ke Yi, Qin Zhang |
| 2010 | On Sums of Roots of Unity. | Bruce E. Litow |
| 2010 | Efficient Completely Non-malleable Public Key Encryption. | Benot Libert, Moti Yung |
| 2010 | Composition Theorems in Communication Complexity. | Troy Lee, Shengyu Zhang |
| 2010 | On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi. | Ivan Lanese, Jorge A. Prez, Davide Sangiorgi, Alan Schmitt |
| 2010 | Game Semantics for Call-by-Value Polymorphism. | James Laird |
| 2010 | Finding Is as Easy as Detecting for Quantum Walks. | Hari Krovi, Frdric Magniez, Maris Ozols, Jrmie Roland |
| 2010 | Preprocessing of Min Ones Problems: A Dichotomy. | Stefan Kratsch, Magnus Wahlstrm |
| 2010 | Decomposition Width of Matroids. | Daniel Krl' |
| 2010 | Interval Graphs: Canonical Representation in Logspace. | Johannes Kbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky |
| 2010 | Interval Sorting. | Rosa M. Jimnez, Conrado Martnez |
| 2010 | On the Complexity of Searching in Trees: Average-Case Minimization. | Tobias Jacobs, Ferdinando Cicalese, Eduardo Sany Laber, Marco Molinaro |
| 2010 | Polynomial-Space Approximation of No-Signaling Provers. | Tsuyoshi Ito |
| 2010 | Mergeable Dictionaries. | John Iacono, zgr zkan |
| 2010 | What Is a Pure Functional? | Martin Hofmann, Aleksandr Karbyshev, Helmut Seidl |
| 2010 | On Bisimilarity and Substitution in Presence of Replication. | Daniel Hirschkoff, Damien Pous |
| 2010 | On the Existence of Pure Nash Equilibria in Weighted Congestion Games. | Tobias Harks, Max Klimm |
| 2010 | Streaming Algorithms for Independent Sets. | Bjarni V. Halldrsson, Magns M. Halldrsson, Elena Losievskaja, Mario Szegedy |
| 2010 | The Downward-Closure of Petri Net Languages. | Peter Habermehl, Roland Meyer, Harro Wimmel |
| 2010 | On the Inapproximability of Vertex Cover on | Venkatesan Guruswami, Rishi Saket |
| 2010 | SDP Gaps for 2-to-1 and Other Label-Cover Variants. | Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu |
| 2010 | Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems. | Anupam Gupta, Viswanath Nagarajan, R. Ravi |