| 2010 | 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, October 23-26, 2010 |
| 2010 | A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. Jin-Yi Cai, Xi Chen |
| 2010 | A Fourier-Analytic Approach to Reed-Muller Decoding. Parikshit Gopalan |
| 2010 | A Lower Bound for Dynamic Approximate Membership Data Structures. Shachar Lovett, Ely Porat |
| 2010 | A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis. Moritz Hardt, Guy N. Rothblum |
| 2010 | A Non-linear Lower Bound for Planar Epsilon-Nets. Noga Alon |
| 2010 | A Separator Theorem in Minor-Closed Classes. Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2010 | A Unified Framework for Testing Linear-Invariant Properties. Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira |
| 2010 | Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions. Ran Canetti, Huijia Lin, Rafael Pass |
| 2010 | Agnostically Learning under Permutation Invariant Distributions. Karl Wimmer |
| 2010 | All-Pairs Shortest Paths in O(n Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick |
| 2010 | An Efficient Test for Product States with Applications to Quantum Merlin-Arthur Games. Aram W. Harrow, Ashley Montanaro |
| 2010 | Approaching Optimality for Solving SDD Linear Systems. Ioannis Koutis, Gary L. Miller, Richard Peng |
| 2010 | Approximating Maximum Weight Matching in Near-Linear Time. Ran Duan, Seth Pettie |
| 2010 | Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions. Matthew Andrews |
| 2010 | Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation. Yuriy Arbitman, Moni Naor, Gil Segev |
| 2010 | Black-Box Randomized Reductions in Algorithmic Mechanism Design. Shaddin Dughmi, Tim Roughgarden |
| 2010 | Black-Box, Round-Efficient Secure Computation via Non-malleability Amplification. Hoeteck Wee |
| 2010 | Boosting and Differential Privacy. Cynthia Dwork, Guy N. Rothblum, Salil P. Vadhan |
| 2010 | Bounded Independence Fools Degree-2 Threshold Functions. Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson |
| 2010 | Bounds on Monotone Switching Networks for Directed Connectivity. Aaron Potechin |
| 2010 | Budget Feasible Mechanisms. Yaron Singer |
| 2010 | Clustering with Spectral Norm and the k-Means Algorithm. Amit Kumar, Ravindran Kannan |
| 2010 | Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. Venkatesan Guruswami, Adam D. Smith |
| 2010 | Computational Transition at the Uniqueness Threshold. Allan Sly |
| 2010 | Constructive Algorithms for Discrepancy Minimization. Nikhil Bansal |
| 2010 | Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces. Santosh S. Vempala |
| 2010 | Cryptography against Continuous Memory Attacks. Yevgeniy Dodis, Kristiyan Haralambiev, Adriana López-Alt, Daniel Wichs |
| 2010 | Deciding First-Order Properties for Sparse Graphs. Zdenek Dvorák, Daniel Král, Robin Thomas |
| 2010 | Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. Chandra Chekuri, Jan Vondrák, Rico Zenklusen |
| 2010 | Determinant Sums for Undirected Hamiltonicity. Andreas Björklund |
| 2010 | Distance Oracles beyond the Thorup-Zwick Bound. Mihai Patrascu, Liam Roditty |
| 2010 | Efficient Volume Sampling for Row/Column Subset Selection. Amit Deshpande, Luis Rademacher |
| 2010 | Estimating the Longest Increasing Sequence in Polylogarithmic Time. Michael E. Saks, C. Seshadhri |
| 2010 | Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs. Aleksander Madry |
| 2010 | Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability. Rahul Santhanam |
| 2010 | From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits. Nitin Saxena, C. Seshadhri |
| 2010 | Frugal Mechanism Design via Spectral Techniques. Ning Chen, Edith Elkind, Nick Gravin, Fedor Petrov |
| 2010 | Frugal and Truthful Auctions for Vertex Covers, Flows and Cuts. David Kempe, Mahyar Salek, Cristopher Moore |
| 2010 | Hardness of Finding Independent Sets in Almost 3-Colorable Graphs. Irit Dinur, Subhash Khot, Will Perkins, Muli Safra |
| 2010 | Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP. Jin-Yi Cai, Pinyan Lu, Mingji Xia |
| 2010 | Impossibility of Differentially Private Universally Optimal Mechanisms. Hai Brenner, Kobbi Nissim |
| 2010 | Improved Bounds for Geometric Permutations. Natan Rubin, Haim Kaplan, Micha Sharir |
| 2010 | Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor |
| 2010 | Learning Convex Concepts from Gaussian Distributions with PCA. Santosh S. Vempala |
| 2010 | Local List Decoding with a Constant Number of Queries. Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma |
| 2010 | Logspace Versions of the Theorems of Bodlaender and Courcelle. Michael Elberfeld, Andreas Jakoby, Till Tantau |
| 2010 | Lower Bounds on Near Neighbor Search via Metric Expansion. Rina Panigrahy, Kunal Talwar, Udi Wieder |
| 2010 | Matching Vector Codes. Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin |
| 2010 | Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability. Konstantin Makarychev, Yury Makarychev |
| 2010 | Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time. Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen |
| 2010 | Minimum-Cost Network Design with (Dis)economies of Scale. Matthew Andrews, Spyridon Antonakopoulos, Lisa Zhang |
| 2010 | New Constructive Aspects of the Lovasz Local Lemma. Bernhard Haeupler, Barna Saha, Aravind Srinivasan |
| 2010 | On the Computational Complexity of Coin Flipping. Hemanta K. Maji, Manoj Prabhakaran, Amit Sahai |
| 2010 | On the Insecurity of Parallel Repetition for Leakage Resilience. Allison B. Lewko, Brent Waters |
| 2010 | On the Queue Number of Planar Graphs. Giuseppe Di Battista, Fabrizio Frati, János Pach |
| 2010 | One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk. Ashish Goel, Ian Post |
| 2010 | Optimal Stochastic Planarization. Anastasios Sidiropoulos |
| 2010 | Optimal Testing of Reed-Muller Codes. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman |
| 2010 | Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage. Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz, Vinod Vaikuntanathan |
| 2010 | Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
| 2010 | Polynomial Learning of Distribution Families. Mikhail Belkin, Kaushik Sinha |
| 2010 | Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields. Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka |
| 2010 | Pseudorandom Generators for Regular Branching Programs. Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff |
| 2010 | Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction. Renato Paes Leme, Éva Tardos |
| 2010 | Replacement Paths via Fast Matrix Multiplication. Oren Weimann, Raphael Yuster |
| 2010 | Sequential Rationality in Cryptographic Protocols. Ronen Gradwohl, Noam Livne, Alon Rosen |
| 2010 | Settling the Polynomial Learnability of Mixtures of Gaussians. Ankur Moitra, Gregory Valiant |
| 2010 | Solving Linear Systems through Nested Dissection. Noga Alon, Raphael Yuster |
| 2010 | Stability Yields a PTAS for k-Median and k-Means Clustering. Pranjal Awasthi, Avrim Blum, Or Sheffet |
| 2010 | Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature. David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, Scott M. Summers |
| 2010 | Subcubic Equivalences between Path, Matrix and Triangle Problems. Virginia Vassilevska Williams, Ryan Williams |
| 2010 | Subexponential Algorithms for Unique Games and Related Problems. Sanjeev Arora, Boaz Barak, David Steurer |
| 2010 | Sublinear Optimization for Machine Learning. Kenneth L. Clarkson, Elad Hazan, David P. Woodruff |
| 2010 | Testing Properties of Sparse Images. Gilad Tsur, Dana Ron |
| 2010 | The Coin Problem and Pseudorandomness for Branching Programs. Joshua Brody, Elad Verbin |
| 2010 | The Complexity of Distributions. Emanuele Viola |
| 2010 | The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem. Marcus Isaksson, Guy Kindler, Elchanan Mossel |
| 2010 | The Geometry of Scheduling. Nikhil Bansal, Kirk Pruhs |
| 2010 | The Limits of Two-Party Differential Privacy. Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan |
| 2010 | The Monotone Complexity of k-clique on Random Graphs. Benjamin Rossman |
| 2010 | The Sub-exponential Upper Bound for On-Line Chain Partitioning. Bartlomiej Bosek, Tomasz Krawczyk |
| 2010 | Vertex Sparsifiers and Abstract Rounding Algorithms. Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra |