| 2011 | A Complexity View of Markets with Social Influence. Xi Chen, Shang-Hua Teng |
| 2011 | Abstract Cryptography. Ueli Maurer, Renato Renner |
| 2011 | Best-Response Mechanisms. Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar |
| 2011 | Beyond the Nash Equilibrium Barrier. Robert D. Kleinberg, Katrina Ligett, Georgios Piliouras, Éva Tardos |
| 2011 | Combinatorial Approximation Algorithms for MaxCut using Random Walks. Satyen Kale, C. Seshadhri |
| 2011 | Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes. Konstantin Makarychev, Alantha Newman |
| 2011 | Compression without a common prior: an information-theoretic justification for ambiguity in language. Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, Madhu Sudan |
| 2011 | Computationally Limited Randomness. Matei David, Phuong Nguyen, Periklis A. Papakonstantinou, Anastasios Sidiropoulos |
| 2011 | Cross-Validation and Mean-Square Stability. Satyen Kale, Ravi Kumar, Sergei Vassilvitskii |
| 2011 | Cycle Detection, Order Finding and Discrete Log with Jumps. Sourav Chakraborty, David García-Soriano, Arie Matsliah |
| 2011 | Distributed Computing with Adaptive Heuristics. Aaron D. Jaggard, Michael Schapira, Rebecca N. Wright |
| 2011 | Economical Graph Discovery. Noga Alon, Yuval Emek, Michal Feldman, Moshe Tennenholtz |
| 2011 | Efficient Semantic Communication via Compatible Beliefs. Brendan Juba, Madhu Sudan |
| 2011 | Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods. Maurice J. Jansen |
| 2011 | Fast Local Computation Algorithms. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie |
| 2011 | Finding Almost-Perfect Graph Bisections. Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou |
| 2011 | Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Henry Cohn, Nadia Heninger |
| 2011 | Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings Bernard Chazelle |
| 2011 | Is Submodularity Testable? C. Seshadhri, Jan Vondrák |
| 2011 | Leaky Pseudo-Entropy Functions. Mark Braverman, Avinatan Hassidim, Yael Tauman Kalai |
| 2011 | On Approximating the Entropy of Polynomial Mappings. Zeev Dvir, Dan Gutfreund, Guy N. Rothblum, Salil P. Vadhan |
| 2011 | Optimal lower bounds for locality sensitive hashing (except when q is tiny). Ryan O'Donnell, Yi Wu, Yuan Zhou |
| 2011 | Posting Prices with Unknown Distributions. Moshe Babaioff, Liad Blumrosen, Shaddin Dughmi, Yaron Singer |
| 2011 | Pricing Loss Leaders can be Hard. Yi Wu |
| 2011 | Property Testing via Set-Theoretic Operations. Victor Chen, Madhu Sudan, Ning Xie |
| 2011 | Query Complexity Lower Bounds for Reconstruction of Codes. Sourav Chakraborty, Eldar Fischer, Arie Matsliah |
| 2011 | Renegotiation-Safe Protocols. Rafael Pass, Abhi Shelat |
| 2011 | Revenue Maximization via Nash Implementation. Thành Nguyen |
| 2011 | Secret Sharing Krohn-Rhodes: Private and Perennial Distributed Computation. Shlomi Dolev, Juan A. Garay, Niv Gilboa, Vladimir Kolesnikov |
| 2011 | Semantic Security under Related-Key Attacks and Applications. Benny Applebaum, Danny Harnik, Yuval Ishai |
| 2011 | Shallow circuits with high-powered inputs. Pascal Koiran |
| 2011 | Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick |
| 2011 | Testing Properties of Collections of Distributions. Reut Levi, Dana Ron, Ronitt Rubinfeld |
| 2011 | Testing monotonicity of distributions over general partial orders. Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant |
| 2011 | The Complexity of Linear Dependence Problems in Vector Spaces. Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie |
| 2011 | The Effects of Diversity in Aggregation Games. Petros Mol, Andrea Vattani, Panagiotis Voulgaris |
| 2011 | The Hitchhiker's Guide to Affiliation Networks: A Game-Theoretic Approach. Christian Borgs, Jennifer T. Chayes, Jian Ding, Brendan Lucier |
| 2011 | The Need for Structure in Quantum Speedups. Scott Aaronson, Andris Ambainis |
| 2011 | Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. Eli Ben-Sasson, Jakob Nordström |