| 2010 | 1-Pass Relative-Error L Morteza Monemizadeh, David P. Woodruff |
| 2010 | A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model. Bahman Bahmani, Aranyak Mehta, Rajeev Motwani |
| 2010 | A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover. Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy |
| 2010 | A Deterministic Truthful PTAS for Scheduling Related Machines. George Christodoulou, Annamária Kovács |
| 2010 | A Fourier Space Algorithm for Solving Quadratic Assignment Problems. Risi Kondor |
| 2010 | A Locality-Sensitive Hash for Real Vectors. Tyler Neylon |
| 2010 | A Max-Flow/Min-Cut Algorithm for a Class of Wireless Networks. S. M. Sadegh Tabatabaei Yazdi, Serap A. Savari |
| 2010 | A Model of Computation for MapReduce. Howard J. Karloff, Siddharth Suri, Sergei Vassilvitskii |
| 2010 | A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs. Aaron Bernstein |
| 2010 | A Polynomial Time Approximation Scheme for k-Consensus Clustering. Tom Coleman, Anthony Wirth |
| 2010 | A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics. T.-H. Hubert Chan, Khaled M. Elbassioni |
| 2010 | A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing. Aparna Das, Claire Mathieu |
| 2010 | A Space-Time Tradeoff for Permutation Problems. Mikko Koivisto, Pekka Parviainen |
| 2010 | Algorithmic Lower Bounds for Problems Parameterized with Clique-Width. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh |
| 2010 | Algorithms and Complexity for Periodic Real-Time Scheduling. Vincenzo Bonifaci, Ho-Leung Chan, Alberto Marchetti-Spaccamela, Nicole Megow |
| 2010 | Algorithms for Ray Class Groups and Hilbert Class Fields. Kirsten Eisenträger, Sean Hallgren |
| 2010 | An (almost) Linear Time Algorithm for Odd Cyles Transversal. Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2010 | An Improved Competitive Algorithm for Reordering Buffer Management. Noa Avigdor-Elgrabli, Yuval Rabani |
| 2010 | An Improved Construction of Progression-Free Sets. Michael Elkin |
| 2010 | An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi |
| 2010 | An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling. Sungjin Im, Benjamin Moseley |
| 2010 | Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures. Seth Pettie |
| 2010 | Approximability of Robust Network Design. Neil Olver, F. Bruce Shepherd |
| 2010 | Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface. Petr Hlinený, Markus Chimani |
| 2010 | Asymmetric Traveling Salesman Path and Directed Latency Problems. Zachary Friggstad, Mohammad R. Salavatipour, Zoya Svitkina |
| 2010 | Basis Reduction and the Complexity of Brand-and-Bound. Gábor Pataki, Mustafa Kemal Tural, Erick B. Wong |
| 2010 | Belief Propagation for Min-cost Network Flow: Convergence & Correctness. David Gamarnik, Devavrat Shah, Yehua Wei |
| 2010 | Bidimensionality and Kernels. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos |
| 2010 | Bounding Variance and Expectation of Longest Path Lengths in DAGs. Jeff Edmonds, Supratik Chakraborty |
| 2010 | Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs. Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, J. Ian Munro |
| 2010 | Cell-Probe Lower Bounds for Succinct Partial Sums. Mihai Patrascu, Emanuele Viola |
| 2010 | Classified Stable Matching. Chien-Chung Huang |
| 2010 | Compact Ancestry Labeling Schemes for XML Trees. Pierre Fraigniaud, Amos Korman |
| 2010 | Convergence, Stability, and Discrete Approximation of Laplace Spectra. Tamal K. Dey, Pawas Ranjan, Yusu Wang |
| 2010 | Coresets and Sketches for High Dimensional Subspace Approximation Problems. Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P. Woodruff |
| 2010 | Correlation Clustering with Noisy Input. Claire Mathieu, Warren Schudy |
| 2010 | Correlation Robust Stochastic Optimization. Shipra Agrawal, Yichuan Ding, Amin Saberi, Yinyu Ye |
| 2010 | Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. Timothy M. Chan, Mihai Patrascu |
| 2010 | Counting Stars and Other Small Subgraphs in Sublinear Time. Mira Gonen, Dana Ron, Yuval Shavitt |
| 2010 | Data Structures for Range Minimum Queries in Multidimensional Arrays. Hao Yuan, Mikhail J. Atallah |
| 2010 | Data-Specific Analysis of String Sorting. Raimund Seidel |
| 2010 | Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs. Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2010 | Deletion Without Rebalancing in Balanced Binary Trees. Siddhartha Sen, Robert Endre Tarjan |
| 2010 | Deterministic Algorithms for the Lovász Local Lemma. Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler |
| 2010 | Differential Privacy in New Settings. Cynthia Dwork |
| 2010 | Differentially Private Combinatorial Optimization. Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar |
| 2010 | Distributed Agreement with Optimal Communication Complexity. Seth Gilbert, Dariusz R. Kowalski |
| 2010 | EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard. Friedrich Eisenbrand, Thomas Rothvoß |
| 2010 | Efficient Broadcast on Random Geometric Graphs. Milan Bradonjic, Robert Elsässer, Tobias Friedrich, Thomas Sauerwald, Alexandre Stauffer |
| 2010 | Efficiently Decodable Non-adaptive Group Testing. Piotr Indyk, Hung Q. Ngo, Atri Rudra |
| 2010 | Energy Efficient Scheduling via Partial Shutdown. Samir Khuller, Jian Li, Barna Saha |
| 2010 | Fast Distance Multiplication of Unit-Monge Matrices. Alexander Tiskin |
| 2010 | Fast SDP Algorithms for Constraint Satisfaction Problems. David Steurer |
| 2010 | Faster Exponential Time Algorithms for the Shortest Vector Problem. Daniele Micciancio, Panagiotis Voulgaris |
| 2010 | Finding the Jaccard Median. Flavio Chierichetti, Ravi Kumar, Sandeep Pandey, Sergei Vassilvitskii |
| 2010 | Flow-Cut Gaps for Integer and Fractional Multiflows. Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel |
| 2010 | Fully-Functional Succinct Trees. Kunihiko Sadakane, Gonzalo Navarro |
| 2010 | Generating a d-dimensional Linear Subspace Efficiently. Raphael Yuster |
| 2010 | Genus and the Geometry of the Cut Graph. James R. Lee, Anastasios Sidiropoulos |
| 2010 | Geometric Optimization and Sums of Algebraic Functions. Antoine Vigneron |
| 2010 | Google's Auction for TV Ads. Noam Nisan |
| 2010 | Hardness Results for Homology Localization. Chao Chen, Daniel Freedman |
| 2010 | Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. Ittai Abraham, Amos Fiat, Andrew V. Goldberg, Renato Fonseca F. Werneck |
| 2010 | How Far Can You Reach? Ciprian Borcea, Ileana Streinu |
| 2010 | How Good is the Chord Algorithm?. Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis |
| 2010 | How to Meet Asynchronously (Almost) Everywhere. Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc |
| 2010 | Improved Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting Strolls. Aaron Archer, Anna Blasiak |
| 2010 | Inapproximability for Planar Embedding Problems. Jeff Edmonds, Anastasios Sidiropoulos, Anastasios Zouzias |
| 2010 | Inapproximability for VCG-Based Combinatorial Auctions. David Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer, Christopher Umans |
| 2010 | Incentive Compatible Budget Elicitation in Multi-unit Auctions. Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, Lirong Xia |
| 2010 | Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. Alexandr Andoni, T. S. Jayram, Mihai Patrascu |
| 2010 | Lower Bounds for Sparse Recovery. Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff |
| 2010 | Lower Bounds for Testing Triangle-freeness in Boolean Functions. Arnab Bhattacharyya, Ning Xie |
| 2010 | Maximum Flows and Parametric Shortest Paths in Planar Graphs. Jeff Erickson |
| 2010 | Monotonicity in Bargaining Networks. Yossi Azar, Nikhil R. Devanur, Kamal Jain, Yuval Rabani |
| 2010 | Near-Optimal Sublinear Time Algorithms for Ulam Distance. Alexandr Andoni, Huy L. Nguyen |
| 2010 | On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic. Stephan Kreutzer, Siamak Tazari |
| 2010 | On Linear and Semidefinite Programming Relaxations for Hypergraph Matching. Yuk Hei Chan, Lap Chi Lau |
| 2010 | On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Füredi-Hajnal Conjecture. Seth Pettie |
| 2010 | On the Cell Probe Complexity of Dynamic Membership. Ke Yi, Qin Zhang |
| 2010 | On the Equilibria of Alternating Move Games. Aaron Roth, Maria-Florina Balcan, Adam Kalai, Yishay Mansour |
| 2010 | On the Exact Space Complexity of Sketching and Streaming Small Norms. Daniel M. Kane, Jelani Nelson, David P. Woodruff |
| 2010 | On the Optimality of Spiral Search. Elmar Langetepe |
| 2010 | On the Possibility of Faster SAT Algorithms. Mihai Patrascu, Ryan Williams |
| 2010 | One-Counter Markov Decision Processes. Tomás Brázdil, Václav Brozek, Kousha Etessami, Antonín Kucera, Dominik Wojtczak |
| 2010 | Online Learning with Queries. Chao-Kai Chiang, Chi-Jen Lu |
| 2010 | Optimally Reconstructing Weighted Graphs Using Queries. Hanna Mazzawi |
| 2010 | Orthogonal Ham-Sandwich Theorem in R Sergey Bereg |
| 2010 | PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs. David Gamarnik, David A. Goldberg, Theophane Weber |
| 2010 | Paired Approximation Problems and Incompatible Inapproximabilities. David Eppstein |
| 2010 | Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph. Attila Bernáth, Roland Grappe, Zoltán Szigeti |
| 2010 | Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees. Prasad Tetali, Juan Carlos Vera, Eric Vigoda, Linji Yang |
| 2010 | Price of Anarchy for Greedy Auctions. Brendan Lucier, Allan Borodin |
| 2010 | Pricing Randomized Allocations. Patrick Briest, Shuchi Chawla, Robert Kleinberg, S. Matthew Weinberg |
| 2010 | Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications. Anthony Man-Cho So |
| 2010 | Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010 Moses Charikar |
| 2010 | Property Testing and Parameter Testing for Permutations. Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo T. de A. Moreira, Rudini Menezes Sampaio |
| 2010 | Quantum Algorithms for Highly Non-Linear Boolean Functions. Martin Rötteler |
| 2010 | Quasirandom Load Balancing. Tobias Friedrich, Martin Gairing, Thomas Sauerwald |
| 2010 | Randomized Shellsort: A Simple Oblivious Sorting Algorithm. Michael T. Goodrich |
| 2010 | Recognizing a Totally Odd K Ken-ichi Kawarabayashi, Zhentao Li, Bruce A. Reed |
| 2010 | Reconstructing Approximate Phylogenetic Trees from Quartet Samples. Sagi Snir, Raphael Yuster |
| 2010 | Region Growing for Multi-Route Cuts. Siddharth Barman, Shuchi Chawla |
| 2010 | Regular Expression Matching with Multi-Strings and Intervals. Philip Bille, Mikkel Thorup |
| 2010 | Resource Minimization for Fire Containment. Parinya Chalermsook, Julia Chuzhoy |
| 2010 | Road Network Reconstruction for Organizing Paths. Daniel Chen, Leonidas J. Guibas, John Hershberger, Jian Sun |
| 2010 | Rumour Spreading and Graph Conductance. Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi |
| 2010 | SRPT is 1.86-Competitive for Completion Time Scheduling. Christine Chung, Tim Nonner, Alexander Souza |
| 2010 | Self-improving Algorithms for Convex Hulls. Kenneth L. Clarkson, Wolfgang Mulzer, C. Seshadhri |
| 2010 | Shape Replication through Self-Assembly and RNase Enzymes. Zachary Abel, Nadia M. Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Y. Flatland, Scott Duke Kominers, Robert Schweller |
| 2010 | Sharp Dichotomies for Regret Minimization in Metric Spaces. Robert Kleinberg, Aleksandrs Slivkins |
| 2010 | Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities. Subhash Khot, Assaf Naor |
| 2010 | Solving MAX-r-SAT Above a Tight Lower Bound. Noga Alon, Gregory Z. Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo |
| 2010 | Solving Simple Stochastic Tail Games. Hugo Gimbert, Florian Horn |
| 2010 | Solving the Replacement Paths Problem for Planar Directed Graphs in O(n log n) Time. Christian Wulff-Nilsen |
| 2010 | Speeding Up Random Walks with Neighborhood Exploration. Petra Berenbrink, Colin Cooper, Robert Elsässer, Tomasz Radzik, Thomas Sauerwald |
| 2010 | Streaming Algorithms for Extent Problems in High Dimensions. Pankaj K. Agarwal, R. Sharathkumar |
| 2010 | Synchrony and Asynchrony in Neural Networks. Fabian Kuhn, Konstantinos Panagiotou, Joel Spencer, Angelika Steger |
| 2010 | Terrain Guarding is NP-Hard. James King, Erik Krohn |
| 2010 | Testing Additive Integrality Gaps. Friedrich Eisenbrand, Nicolai Hähnle, Dömötör Pálvölgyi, Gennady Shmonin |
| 2010 | Testing Monotone Continuous Distributions on High-dimensional Real Cubes. Michal Adamaszek, Artur Czumaj, Christian Sohler |
| 2010 | Testing Planarity of Partially Embedded Graphs. Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, Maurizio Patrignani, Ignaz Rutter |
| 2010 | The (1 + beta)-Choice Process and Weighted Balls-into-Bins. Yuval Peres, Kunal Talwar, Udi Wieder |
| 2010 | The Edge Disjoint Paths Problem in Eulerian Graphs and 4-edge-connected Graphs. Ken-ichi Kawarabayashi, Yusuke Kobayashi |
| 2010 | The Focus of Attention Problem. Dries R. Goossens, Sergey Polyakovskiy, Frits C. R. Spieksma, Gerhard J. Woeginger |
| 2010 | The Forest Hiding Problem. Adrian Dumitrescu, Minghui Jiang |
| 2010 | The Power of Convex Relaxation: The Surprising Stories of Matrix Completion and Compressed Sensing. Emmanuel J. Candès |
| 2010 | The Rank of Diluted Random Graphs. Charles Bordenave, Marc Lelarge |
| 2010 | The Scaling Window for a Random Graph with a Given Degree Sequence. Hamed Hatami, Michael Molloy |
| 2010 | Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies. Karthekeyan Chandrasekaran, Daniel Dadush, Santosh S. Vempala |
| 2010 | Towards a Calculus for Non-Linear Spectral Gaps. Manor Mendel, Assaf Naor |
| 2010 | Towards the Randomized k-Server Conjecture: A Primal-Dual Approach. Nikhil Bansal, Niv Buchbinder, Joseph Naor |
| 2010 | Tree Embeddings for Two-Edge-Connected Network Design. Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi |
| 2010 | Universal epsilon-approximators for Integrals. Michael Langberg, Leonard J. Schulman |
| 2010 | Utilitarian Mechanism Design for Multi-Objective Optimization. Fabrizio Grandoni, Piotr Krysta, Stefano Leonardi, Carmine Ventre |
| 2010 | Vertices of Degree k in Random Maps. Daniel Johannsen, Konstantinos Panagiotou |