| 2010 | Recognizing a Totally Odd K | Ken-ichi Kawarabayashi, Zhentao Li, Bruce A. Reed |
| 2010 | The Edge Disjoint Paths Problem in Eulerian Graphs and 4-edge-connected Graphs. | Ken-ichi Kawarabayashi, Yusuke Kobayashi |
| 2010 | A Model of Computation for MapReduce. | Howard J. Karloff, Siddharth Suri, Sergei Vassilvitskii |
| 2010 | On the Exact Space Complexity of Sketching and Streaming Small Norms. | Daniel M. Kane, Jelani Nelson, David P. Woodruff |
| 2010 | Vertices of Degree k in Random Maps. | Daniel Johannsen, Konstantinos Panagiotou |
| 2010 | Efficiently Decodable Non-adaptive Group Testing. | Piotr Indyk, Hung Q. Ngo, Atri Rudra |
| 2010 | An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling. | Sungjin Im, Benjamin Moseley |
| 2010 | Classified Stable Matching. | Chien-Chung Huang |
| 2010 | Property Testing and Parameter Testing for Permutations. | Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo T. de A. Moreira, Rudini Menezes Sampaio |
| 2010 | Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface. | Petr Hlinen, Markus Chimani |
| 2010 | The Scaling Window for a Random Graph with a Given Degree Sequence. | Hamed Hatami, Michael Molloy |
| 2010 | Differentially Private Combinatorial Optimization. | Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar |
| 2010 | Tree Embeddings for Two-Edge-Connected Network Design. | Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi |
| 2010 | Utilitarian Mechanism Design for Multi-Objective Optimization. | Fabrizio Grandoni, Piotr Krysta, Stefano Leonardi, Carmine Ventre |
| 2010 | The Focus of Attention Problem. | Dries R. Goossens, Sergey Polyakovskiy, Frits C. R. Spieksma, Gerhard J. Woeginger |
| 2010 | Randomized Shellsort: A Simple Oblivious Sorting Algorithm. | Michael T. Goodrich |
| 2010 | Counting Stars and Other Small Subgraphs in Sublinear Time. | Mira Gonen, Dana Ron, Yuval Shavitt |
| 2010 | Solving Simple Stochastic Tail Games. | Hugo Gimbert, Florian Horn |
| 2010 | Distributed Agreement with Optimal Communication Complexity. | Seth Gilbert, Dariusz R. Kowalski |
| 2010 | Belief Propagation for Min-cost Network Flow: Convergence & Correctness. | David Gamarnik, Devavrat Shah, Yehua Wei |
| 2010 | PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs. | David Gamarnik, David A. Goldberg, Theophane Weber |
| 2010 | Asymmetric Traveling Salesman Path and Directed Latency Problems. | Zachary Friggstad, Mohammad R. Salavatipour, Zoya Svitkina |
| 2010 | Quasirandom Load Balancing. | Tobias Friedrich, Martin Gairing, Thomas Sauerwald |
| 2010 | Compact Ancestry Labeling Schemes for XML Trees. | Pierre Fraigniaud, Amos Korman |
| 2010 | Bidimensionality and Kernels. | Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos |