| 2011 | (1 + eps)-Approximate Sparse Recovery. Eric Price, David P. Woodruff |
| 2011 | 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General. Timon Hertli |
| 2011 | A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths. Paul S. Bonsma, Jens Schulz, Andreas Wiese |
| 2011 | A Nearly-m log n Time Solver for SDD Linear Systems. Ioannis Koutis, Gary L. Miller, Richard Peng |
| 2011 | A Parallel Approximation Algorithm for Positive Semidefinite Programming. Rahul Jain, Penghui Yao |
| 2011 | A Polylogarithmic-Competitive Algorithm for the k-Server Problem. Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor |
| 2011 | A Randomized Rounding Approach to the Traveling Salesman Problem. Shayan Oveis Gharan, Amin Saberi, Mohit Singh |
| 2011 | A Small PRG for Polynomial Threshold Functions of Gaussians. Daniel M. Kane |
| 2011 | A Two Prover One Round Game with Strong Soundness. Subhash Khot, Muli Safra |
| 2011 | A Unified Continuous Greedy Algorithm for Submodular Maximization. Moran Feldman, Joseph Naor, Roy Schwartz |
| 2011 | Algorithms for the Generalized Sorting Problem. Zhiyi Huang, Sampath Kannan, Sanjeev Khanna |
| 2011 | An Algebraic Proof of a Robust Social Choice Impossibility Theorem. Dvir Falik, Ehud Friedgut |
| 2011 | An FPTAS for #Knapsack and Related Counting Problems. Parikshit Gopalan, Adam R. Klivans, Raghu Meka, Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda |
| 2011 | Approximating Graphic TSP by Matchings. Tobias Mömke, Ola Svensson |
| 2011 | Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits. Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi |
| 2011 | Approximation Algorithms for Submodular Multiway Partition. Chandra Chekuri, Alina Ene |
| 2011 | Balls and Bins: Smaller Hash Families and Faster Evaluation. L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder |
| 2011 | Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. Saeed Alaei |
| 2011 | Coin Flipping with Constant Bias Implies One-Way Functions. Iftach Haitner, Eran Omri |
| 2011 | Computing Blindfolded: New Developments in Fully Homomorphic Encryption. Vinod Vaikuntanathan |
| 2011 | Delays and the Capacity of Continuous-Time Channels. Sanjeev Khanna, Madhu Sudan |
| 2011 | Dispersers for Affine Sources with Sub-polynomial Entropy. Ronen Shaltiel |
| 2011 | Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games. Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik |
| 2011 | Efficient Fully Homomorphic Encryption from (Standard) LWE. Zvika Brakerski, Vinod Vaikuntanathan |
| 2011 | Efficient Reconstruction of Random Multilinear Formulas. Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam |
| 2011 | Efficient and Explicit Coding for Interactive Communication. Ran Gelles, Ankur Moitra, Amit Sahai |
| 2011 | Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings. Daniel Dadush, Chris Peikert, Santosh S. Vempala |
| 2011 | Evolution with Recombination. Varun Kanade |
| 2011 | Extractors for Circuit Sources. Emanuele Viola |
| 2011 | Extreme-Value Theorems for Optimal Multidimensional Pricing. Yang Cai, Constantinos Daskalakis |
| 2011 | Fully Dynamic Maximal Matching in O (log n) Update Time. Surender Baswana, Manoj Gupta, Sandeep Sen |
| 2011 | Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits. Craig Gentry, Shai Halevi |
| 2011 | Graph Connectivities, Network Coding, and Expander Graphs. Ho Yee Cheung, Lap Chi Lau, Kai Man Leung |
| 2011 | Green Computing Algorithmics. Kirk Pruhs |
| 2011 | How Bad is Forming Your Own Opinion? David Bindel, Jon M. Kleinberg, Sigal Oren |
| 2011 | How to Garble Arithmetic Circuits. Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
| 2011 | How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. Alexandra Kolla, Konstantin Makarychev, Yury Makarychev |
| 2011 | IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011 Rafail Ostrovsky |
| 2011 | Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets. Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, Eric Vigoda, Linji Yang |
| 2011 | Information Equals Amortized Communication. Mark Braverman, Anup Rao |
| 2011 | Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. Venkatesan Guruswami, Ali Kemal Sinop |
| 2011 | Lexicographic Products and the Power of Non-linear Network Coding. Anna Blasiak, Robert Kleinberg, Eyal Lubetzky |
| 2011 | Limitations of Randomized Mechanisms for Combinatorial Auctions. Shaddin Dughmi, Jan Vondrák |
| 2011 | Local Distributed Decision. Pierre Fraigniaud, Amos Korman, David Peleg |
| 2011 | Markov Layout. Flavio Chierichetti, Ravi Kumar, Prabhakar Raghavan |
| 2011 | Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems. Jian Li, Amol Deshpande |
| 2011 | Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2. Loïc Seguin-Charbonneau, F. Bruce Shepherd |
| 2011 | Mechanism Design with Set-Theoretic Beliefs. Jing Chen, Silvio Micali |
| 2011 | Medium Access Using Queues. Devavrat Shah, Jinwoo Shin, Prasad Tetali |
| 2011 | Min-max Graph Partitioning and Small Set Expansion. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz |
| 2011 | Minimum Weight Cycles and Triangles: Equivalences and Algorithms. Liam Roditty, Virginia Vassilevska Williams |
| 2011 | Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen |
| 2011 | Mutual Exclusion with O(log^2 Log n) Amortized Work. Michael A. Bender, Seth Gilbert |
| 2011 | Near Linear Lower Bound for Dimension Reduction in L1. Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen |
| 2011 | Near Optimal Column-Based Matrix Reconstruction. Christos Boutsidis, Petros Drineas, Malik Magdon-Ismail |
| 2011 | New Extension of the Weil Bound for Character Sums with Applications to Coding. Tali Kaufman, Shachar Lovett |
| 2011 | On Range Searching in the Group Model and Combinatorial Discrepancy. Kasper Green Larsen |
| 2011 | On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems. Dorit Aharonov, Lior Eldar |
| 2011 | On the Power of Adaptivity in Sparse Recovery. Piotr Indyk, Eric Price, David P. Woodruff |
| 2011 | Online Node-Weighted Steiner Tree and Related Problems. Joseph Naor, Debmalya Panigrahi, Mohit Singh |
| 2011 | Optimal Bounds for Quantum Bit Commitment. André Chailloux, Iordanis Kerenidis |
| 2011 | Optimal Testing of Multivariate Polynomials over Small Prime Fields. Elad Haramaty, Amir Shpilka, Madhu Sudan |
| 2011 | Planar Graphs: Random Walks and Bipartiteness Testing. Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler |
| 2011 | Privacy Amplification and Non-malleable Extractors via Character Sums. Yevgeniy Dodis, Xin Li, Trevor D. Wooley, David Zuckerman |
| 2011 | Pseudorandomness for Read-Once Formulas. Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan |
| 2011 | Quadratic Goldreich-Levin Theorems. Madhur Tulsiani, Julia Wolf |
| 2011 | Quantum Query Complexity of State Conversion. Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy |
| 2011 | Randomness Buys Depth for Approximate Counting. Emanuele Viola |
| 2011 | Rounding Semidefinite Programming Hierarchies via Global Correlation. Boaz Barak, Prasad Raghavendra, David Steurer |
| 2011 | Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications. Christian Wulff-Nilsen |
| 2011 | Sharp Mixing Time Bounds for Sampling Random Surfaces. Pietro Caputo, Fabio Martinelli, Fabio Lucio Toninelli |
| 2011 | Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk |
| 2011 | Stateless Cryptographic Protocols. Vipul Goyal, Hemanta K. Maji |
| 2011 | Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones. Michael Elkin, Shay Solomon |
| 2011 | Storing Secrets on Continually Leaky Devices. Yevgeniy Dodis, Allison B. Lewko, Brent Waters, Daniel Wichs |
| 2011 | Streaming Algorithms via Precision Sampling. Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
| 2011 | Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. Madhav Jha, Sofya Raskhodnikova |
| 2011 | The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach. Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani |
| 2011 | The Complexity of Renaming. Dan Alistarh, James Aspnes, Seth Gilbert, Rachid Guerraoui |
| 2011 | The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani |
| 2011 | The Graph Minor Algorithm with Parity Conditions. Ken-ichi Kawarabayashi, Bruce A. Reed, Paul Wollan |
| 2011 | The Grothendieck Constant is Strictly Smaller than Krivine's Bound. Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor |
| 2011 | The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable. Ken-ichi Kawarabayashi, Mikkel Thorup |
| 2011 | The Power of Linear Estimators. Gregory Valiant, Paul Valiant |
| 2011 | The Promise of Differential Privacy: A Tutorial on Algorithmic Techniques. Cynthia Dwork |
| 2011 | The Randomness Complexity of Parallel Repetition. Kai-Min Chung, Rafael Pass |
| 2011 | Tight Lower Bounds for 2-query LCCs over Finite Fields. Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, Shubhangi Saraf |
| 2011 | Welfare and Profit Maximization with Production Costs. Avrim Blum, Anupam Gupta, Yishay Mansour, Ankit Sharma |
| 2011 | Which Networks are Least Susceptible to Cascading Failures? Lawrence E. Blume, David A. Easley, Jon M. Kleinberg, Robert Kleinberg, Éva Tardos |