| 2009 | An Observation on Non-Malleable Witness-Indistinguishability and Non-Malleable Zero-Knowledge. | Zongyang Zhang, Zhenfu Cao, Rong Ma |
| 2009 | The Two-Guard Polygon Walk Problem. | John Z. Zhang |
| 2009 | Polynomial-Time Algorithm for Sorting by Generalized Translocations. | Xiao Yin, Daming Zhu |
| 2009 | Feasibility of Motion Planning on Directed Graphs. | Zhilin Wu, Stphane Grumbach |
| 2009 | Greedy Local Search and Vertex Cover in Sparse Random Graphs. | Carsten Witt |
| 2009 | On the Tractability of Maximal Strip Recovery. | Lusheng Wang, Binhai Zhu |
| 2009 | An Online Algorithm for Applying Reinforcement Learning to Handle Ambiguity in Spoken Dialogues. | Fangju Wang, Kyle Swegles |
| 2009 | A Fixed-Parameter Enumeration Algorithm for the Weighted FVS Problem. | Jianxin Wang, Guohong Jiang |
| 2009 | Constraints, Graphs, Algebra, Logic, and Complexity. | Moshe Y. Vardi |
| 2009 | Neural Computations That Support Long Mixed Sequences of Knowledge Acquisition Tasks. | Leslie G. Valiant |
| 2009 | On the Complexity of the Multiple Stack TSP, kSTSP. | Sophie Toulouse, Roberto Wolfler Calvo |
| 2009 | High Minimal Pairs in the Enumeration Degrees. | Andrea Sorbi, Guohua Wu, Yue Yang |
| 2009 | Strong Positive Reducibilities. | Andrea Sorbi |
| 2009 | Terminal Coalgebras for Measure-Polynomial Functors. | Christoph Schubert |
| 2009 | Best-Order Streaming Model. | Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai |
| 2009 | Exact and Experimental Algorithms for a Huffman-Based Error Detecting Code. | Paulo Eustquio Duarte Pinto, Fbio Protti, Jayme Luiz Szwarcfiter |
| 2009 | Minimizing AND-EXOR Expressions for Multiple-Valued Two-Input Logic Functions. | Takaaki Mizuki, Hitoshi Tsubata, Takao Nishizeki |
| 2009 | A Simple Greedy Algorithm for the k-Disjoint Flow Problem. | Maren Martens |
| 2009 | Linear Kernel for Planar Connected Dominating Set. | Daniel Lokshtanov, Matthias Mnich, Saket Saurabh |
| 2009 | An Almost Totally Universal Tile Set. | Grgory Lafitte, Michael Weiss |
| 2009 | Kolmogorov Complexity and Combinatorial Methods in Communication Complexity. | Marc Kaplan, Sophie Laplante |
| 2009 | On Spanners of Geometric Graphs. | Iyad A. Kanj |
| 2009 | Searching a Circular Corridor with Two Flashlights. | Bo Jiang, Xuehou Tan |
| 2009 | Preserving Privacy versus Data Retention. | Markus Hinkelmann, Andreas Jakoby |
| 2009 | Distributed Systems and Their Environments. | Matthew Hennessy |