| 2011 | A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model. Thomas Kesselheim |
| 2011 | A Master Theorem for Discrete Divide and Conquer Recurrences. Michael Drmota, Wojciech Szpankowski |
| 2011 | A Nonlinear Approach to Dimension Reduction. Lee-Ad Gottlieb, Robert Krauthgamer |
| 2011 | A Stackelberg Strategy for Routing Flow over Time. Umang Bhaskar, Lisa Fleischer, Elliot Anshelevich |
| 2011 | A complete resolution of the Keller maximum clique problem. Jennifer Debroni, John D. Eblen, Michael A. Langston, Wendy J. Myrvold, Peter W. Shor, Dinesh Weerapurage |
| 2011 | A simple and fast 2-approximation algorithms for the one-warehouse multi-retailers problem. Gautier Stauffer, Guillaume Massonnet, Christophe Rapine, Jean-Philippe Gayon |
| 2011 | A subexponential lower bound for the Random Facet algorithm for Parity Games. Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick |
| 2011 | Algebraic Algorithms for Linear Matroid Parity Problems. Ho Yee Cheung, Lap Chi Lau, Kai Man Leung |
| 2011 | Algorithms and Hardness for Subspace Approximation. Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi |
| 2011 | Algorithms for Implicit Hitting Set Problems. Karthekeyan Chandrasekaran, Richard M. Karp, Erick Moreno-Centeno, Santosh S. Vempala |
| 2011 | An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform. Nir Ailon, Edo Liberty |
| 2011 | An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy. George B. Mertzios |
| 2011 | An Optimal Lower Bound for Buffer Management in Multi-Queue Switches. Marcin Bienkowski |
| 2011 | An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter. Shay Solomon |
| 2011 | An algorithmic decomposition of claw-free graphs leading to an O(n Yuri Faenza, Gianpaolo Oriolo, Gautier Stauffer |
| 2011 | Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge Decomposition. Gary L. Miller, Richard Peng, Russell Schwartz, Charalampos E. Tsourakakis |
| 2011 | Approximate Nearest Neighbor Search for Low Dimensional Queries. Sariel Har-Peled, Nirman Kumar |
| 2011 | Approximating Matrix p-norms. Aditya Bhaskara, Aravindan Vijayaraghavan |
| 2011 | Approximating the Girth. Liam Roditty, Roei Tov |
| 2011 | Approximating the Statistics of various Properties in Randomly Weighted Graphs. Yuval Emek, Amos Korman, Yuval Shavitt |
| 2011 | Bayesian Incentive Compatibility via Fractional Assignments. Xiaohui Bei, Zhiyi Huang |
| 2011 | Bayesian Incentive Compatibility via Matchings. Jason D. Hartline, Robert Kleinberg, Azarakhsh Malekian |
| 2011 | Bidimensionality and EPTAS. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh |
| 2011 | Bin Packing via Discrepancy of Permutations. Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß |
| 2011 | Bounding the Randomized Decision Tree Complexity of Read-Once Boolean Functions. Kazuyuki Amano |
| 2011 | Capacitated Metric Labeling. Matthew Andrews, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Ankur Moitra |
| 2011 | Code Equivalence and Group Isomorphism. László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao |
| 2011 | Collapse. Günter Rote, Uri Zwick |
| 2011 | Coloring random graphs online without creating monochromatic subgraphs. Torsten Mütze, Thomas Rast, Reto Spöhel |
| 2011 | Component structure of the vacant set induced by a random walk on a random graph. Colin Cooper, Alan M. Frieze |
| 2011 | Computational Geometry for Non-Geometers: Recent Developments on Some Classical Problems. Timothy M. Chan |
| 2011 | Computing Replacement Paths in Surface Embedded Graphs. Jeff Erickson, Amir Nayyeri |
| 2011 | Computing Shortest Paths amid Pseudodisks. Danny Z. Chen, Haitao Wang |
| 2011 | Computing the Independence Number of Intersection Graphs. Jacob Fox, János Pach |
| 2011 | Continuous Local Search. Constantinos Daskalakis, Christos H. Papadimitriou |
| 2011 | Counting and detecting small subgraphs via equations and matrix multiplication. Miroslaw Kowaluk, Andrzej Lingas, Eva-Marta Lundell |
| 2011 | Dichotomy for Holant* Problems of Boolean Domain. Jin-Yi Cai, Pinyan Lu, Mingji Xia |
| 2011 | Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound. Yair Bartal, Ben Recht, Leonard J. Schulman |
| 2011 | Distributed Selfish Load Balancing on Networks. Petra Berenbrink, Martin Hoefer, Thomas Sauerwald |
| 2011 | Efficient Sketches for the Set Query Problem. Eric Price |
| 2011 | Efficient algorithms for some special cases of the polynomial equivalence problem. Neeraj Kayal |
| 2011 | Embedding Stacked Polytopes on a Polynomial-Size Grid. Erik D. Demaine, André Schulz |
| 2011 | Exponential Time Improvement for min-wise Based Algorithms. Guy Feigenblat, Ely Porat, Ariel Shiftan |
| 2011 | Fast Convergence of Natural Bargaining Dynamics in Exchange Networks. Yashodhan Kanoria, Mohsen Bayati, Christian Borgs, Jennifer T. Chayes, Andrea Montanari |
| 2011 | Fast Information Spreading in Graphs with Large Weak Conductance. Keren Censor-Hillel, Hadas Shachnai |
| 2011 | Fast, precise and dynamic distance queries. Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty |
| 2011 | Faster Replacement Paths. Virginia Vassilevska Williams |
| 2011 | Faster and Dynamic Algorithms for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic Verification. Krishnendu Chatterjee, Monika Henzinger |
| 2011 | Faster quantum algorithm for evaluating game trees. Ben Reichardt |
| 2011 | Generalized Machine Activation Problems. Jian Li, Samir Khuller |
| 2011 | Graph Coloring via The Probabilistic Method. Bruce A. Reed |
| 2011 | Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu |
| 2011 | Hitting time results for Maker-Breaker games. Sonny Ben-Shimon, Asaf Ferber, Dan Hefetz, Michael Krivelevich |
| 2011 | I/O-Efficient Contour Queries on Terrains. Pankaj K. Agarwal, Thomas Mølhave, Bardia Sadri |
| 2011 | Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage Structures. Mark de Berg, Herman J. Haverkort, Constantinos P. Tsirogiannis |
| 2011 | Improved Approximation Results for Stochastic Knapsack Problems. Anand Bhalgat, Ashish Goel, Sanjeev Khanna |
| 2011 | Improved Bound for the Union of Fat Triangles. Esther Ezra, Boris Aronov, Micha Sharir |
| 2011 | Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components. Jakub Lacki |
| 2011 | Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions. Aaron Bernstein, Liam Roditty |
| 2011 | Improved Space Bounds for Cache-Oblivious Range Reporting. Peyman Afshani, Norbert Zeh |
| 2011 | Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal. Daniel Lokshtanov, Dániel Marx, Saket Saurabh |
| 2011 | Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games. Tim Roughgarden, Florian Schoppmann |
| 2011 | Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication. Avner Magen, Anastasios Zouzias |
| 2011 | Matroid Secretary Problem in the Random Assignment Model. José A. Soto |
| 2011 | Mechanism Design via Correlation Gap. Qiqi Yan |
| 2011 | Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers. Jeff Erickson, Amir Nayyeri |
| 2011 | Mobile Geometric Graphs: Detection, Coverage and Percolation. Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer |
| 2011 | Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding. Chandra Chekuri, Jan Vondrák, Rico Zenklusen |
| 2011 | Multicommodity Facility Location under Group Steiner Access Cost. Laura J. Poplawski, Rajmohan Rajaraman |
| 2011 | Near-Optimal No-Regret Algorithms for Zero-Sum Games. Constantinos Daskalakis, Alan Deckelbaum, Anthony Kim |
| 2011 | Nearly Tight Bounds for Testing Function Isomorphism. Sourav Chakraborty, David García-Soriano, Arie Matsliah |
| 2011 | Networks of random cycles. Colin Cooper, Martin E. Dyer, Andrew J. Handley |
| 2011 | New Approximation Algorithms for Minimum Enclosing Convex Shapes. Ankan Saha, S. V. N. Vishwanathan, Xinhua Zhang |
| 2011 | On Belief Propagation Guided Decimation for Random k-SAT. Amin Coja-Oghlan |
| 2011 | On Buffon Machines and Numbers. Philippe Flajolet, Maryse Pelletier, Michèle Soria |
| 2011 | On Graph Crossing Number and Edge Planarization. Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos |
| 2011 | On LP-Based Approximability for Strict CSPs. Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi |
| 2011 | On Minmax Theorems for Multiplayer Games. Yang Cai, Constantinos Daskalakis |
| 2011 | On Parity Check (0, 1)-Matrix over Z Nader H. Bshouty, Hanna Mazzawi |
| 2011 | On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs. Xin He, Huaming Zhang |
| 2011 | On independent sets in random graphs. Amin Coja-Oghlan, Charilaos Efthymiou |
| 2011 | On the Approximability of Budget Feasible Mechanisms. Ning Chen, Nick Gravin, Pinyan Lu |
| 2011 | On the Complexity of Approximating a Nash Equilibrium. Constantinos Daskalakis |
| 2011 | On the Complexity of Time-Dependent Shortest Paths. Luca Foschini, John Hershberger, Subhash Suri |
| 2011 | On the Degree Distribution of Random Planar Graphs. Konstantinos Panagiotou, Angelika Steger |
| 2011 | On the Randomness Requirements of Rumor Spreading. George Giakkoupis, Philipp Woelfel |
| 2011 | Online Scalable Algorithm for Minimizing ℓk-norms of Weighted Flow Time On Unrelated Machines. Sungjin Im, Benjamin Moseley |
| 2011 | Online Scalable Scheduling for the ℓk-norms of Flow Time Without Conservation of Work. Jeff Edmonds, Sungjin Im, Benjamin Moseley |
| 2011 | Online Scheduling on Identical Machines using SRPT. Kyle Fox, Benjamin Moseley |
| 2011 | Online Stochastic Matching: Online Actions Based on Offline Statistics. Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi |
| 2011 | Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations. Gagan Aggarwal, Gagan Goel, Chinmay Karande, Aranyak Mehta |
| 2011 | Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error. T. S. Jayram, David P. Woodruff |
| 2011 | Optimal pattern matching in LZW compressed strings. Pawel Gawrychowski |
| 2011 | Ordered and Unordered Top-K Range Reporting in Large Data Sets. Peyman Afshani, Gerth Stølting Brodal, Norbert Zeh |
| 2011 | Overlap properties of geometric expanders. Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, János Pach |
| 2011 | Packing tight Hamilton cycles in 3-uniform hypergraphs. Alan M. Frieze, Michael Krivelevich, Po-Shen Loh |
| 2011 | Persistent Predecessor Search and Orthogonal point Location on the Word RAM. Timothy M. Chan |
| 2011 | Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees. Ricardo Restrepo, Daniel Stefankovic, Juan Carlos Vera, Eric Vigoda, Linji Yang |
| 2011 | Pricing on Paths: A PTAS for the Highway Problem. Fabrizio Grandoni, Thomas Rothvoß |
| 2011 | Prize-collecting Steiner Problems on Planar Graphs. MohammadHossein Bateni, Chandra Chekuri, Alina Ene, Mohammad Taghi Hajiaghayi, Nitish Korula, Dániel Marx |
| 2011 | Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011 Dana Randall |
| 2011 | Random Access to grammar-Compressed Strings. Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, Oren Weimann |
| 2011 | Randomized Diffusion for Indivisible Loads. Petra Berenbrink, Colin Cooper, Tom Friedetzky, Tobias Friedrich, Thomas Sauerwald |
| 2011 | Randomized Variants of Johnson's Algorithm for MAX SAT. Matthias Poloczek, Georg Schnitger |
| 2011 | Randomized greedy: new variants of some classic approximation algorithms. Kevin P. Costello, Asaf Shapira, Prasad Tetali |
| 2011 | Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures. Allan Grønlund Jørgensen, Kasper Green Larsen |
| 2011 | Ranking with Submodular Valuations. Yossi Azar, Iftah Gamzu |
| 2011 | Reflections for quantum query algorithms. Ben Reichardt |
| 2011 | Risk-Averse Stochastic Optimization: Probabilistically-Constrained Models and Algorithms for Black-Box Distributions. Chaitanya Swamy |
| 2011 | Rumor Spreading and Vertex Expansion on Regular Graphs. Thomas Sauerwald, Alexandre Stauffer |
| 2011 | Secretary Problems: Laminar Matroid and Interval Scheduling. Sungjin Im, Yajun Wang |
| 2011 | Shortest Non-Crossing Walks in the Plane. Jeff Erickson, Amir Nayyeri |
| 2011 | Slightly Superexponential Parameterized Problems. Daniel Lokshtanov, Dániel Marx, Saket Saurabh |
| 2011 | Streaming k-means on Well-Clusterable Data. Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku |
| 2011 | Submodular Maximization by Simulated Annealing. Shayan Oveis Gharan, Jan Vondrák |
| 2011 | Subsampling Mathematical Relaxations and Average-case Complexity. Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer |
| 2011 | Survivable Network Design Problems in Wireless Networks. Debmalya Panigrahi |
| 2011 | Temperature 1 Self-Assembly: Deterministic Assembly in 3D and Probabilistic Assembly in 2D. Matthew Cook, Yunhui Fu, Robert Schweller |
| 2011 | The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus. Shayan Oveis Gharan, Amin Saberi |
| 2011 | The Dichotomy of List Homomorphisms for Digraphs. Pavol Hell, Arash Rafiey |
| 2011 | The Local Lemma is Tight for SAT. Heidi Gebauer, Tibor Szabó, Gábor Tardos |
| 2011 | The Matroid Median Problem. Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, Barna Saha |
| 2011 | The Multiple-Orientability Thresholds for Random Hypergraphs. Nikolaos Fountoulakis, Megha Khosla, Konstantinos Panagiotou |
| 2011 | The Power of Nondeterminism in Self-Assembly. Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki |
| 2011 | The Rigidity Transition in Random Graphs. Shiva Prasad Kasiviswanathan, Cristopher Moore, Louis Theran |
| 2011 | The Streaming Complexity of Cycle Counting, Sorting by Reversals, and Other Problems. Elad Verbin, Wei Yu |
| 2011 | The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. Venkatesan Guruswami, Ali Kemal Sinop |
| 2011 | The maximum size of a Sidon set contained in a sparse random set of integers. Yoshiharu Kohayakawa, Sangjune Lee, Vojtech Rödl |
| 2011 | The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem). Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk |
| 2011 | Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set. Venkatesan Guruswami, Yuan Zhou |
| 2011 | Tight Hardness Results for Minimizing Discrepancy. Moses Charikar, Alantha Newman, Aleksandar Nikolov |
| 2011 | Top-K Color Queries for Document Retrieval. Marek Karpinski, Yakov Nekrich |
| 2011 | Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition. Lorenzo Orecchia, Nisheeth K. Vishnoi |
| 2011 | Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent. Maarten Löffler, Wolfgang Mulzer |
| 2011 | Welfare Guarantees for Combinatorial Auctions with Item Bidding. Kshipra Bhawalkar, Tim Roughgarden |
| 2011 | Where computer vision needs help from computer science. William T. Freeman |
| 2011 | Wireless Capacity with Oblivious Power in General Metrics. Magnús M. Halldórsson, Pradipta Mitra |