| 2013 | A characterization of approximation resistance for even k-partite CSPs. Per Austrin, Subhash Khot |
| 2013 | A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games. Ben W. Reichardt, Falk Unger, Umesh V. Vazirani |
| 2013 | Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. Damien Woods, Ho-Lin Chen, Scott Goodfriend, Nadine Dabby, Erik Winfree, Peng Yin |
| 2013 | Adversary lower bound for the k-sum problem. Aleksandrs Belovs, Robert Spalek |
| 2013 | An energy complexity model for algorithms. Swapnoneel Roy, Atri Rudra, Akshat Verma |
| 2013 | An equational approach to secure multi-party computation. Daniele Micciancio, Stefano Tessaro |
| 2013 | Approaching utopia: strong truthfulness and externality-resistant mechanisms. Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Angelina Vidali |
| 2013 | Barriers in cryptography with weak, correlated and leaky sources. Daniel Wichs |
| 2013 | Can theories be tested?: a cryptographic treatment of forecast testing. Kai-Min Chung, Edward Lui, Rafael Pass |
| 2013 | Catch them if you can: how to serve impatient users. Marek Cygan, Matthias Englert, Anupam Gupta, Marcin Mucha, Piotr Sankowski |
| 2013 | Characterizing the sample complexity of private learners. Amos Beimel, Kobbi Nissim, Uri Stemmer |
| 2013 | Competing provers protocols for circuit evaluation. Gillat Kol, Ran Raz |
| 2013 | Differentially private data analysis of social networks via restricted sensitivity. Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet |
| 2013 | Evasiveness through a circuit lens. Raghav Kulkarni |
| 2013 | Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract. Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer |
| 2013 | H-wise independence. Ishay Haviv, Michael Langberg |
| 2013 | Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013 Robert D. Kleinberg |
| 2013 | Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. Nicole Megow, Julián Mestre |
| 2013 | Is privacy compatible with truthfulness? David Xiao |
| 2013 | Learnability of DNF with representation-specific queries. Liu Yang, Avrim Blum, Jaime G. Carbonell |
| 2013 | Learning and incentives in user-generated content: multi-armed bandits with endogenous arms. Arpita Ghosh, Patrick Hummel |
| 2013 | Learning mixtures of spherical gaussians: moment methods and spectral decompositions. Daniel J. Hsu, Sham M. Kakade |
| 2013 | Low-weight halfspaces for sparse boolean vectors. Philip M. Long, Rocco A. Servedio |
| 2013 | Making evolution rigorous: the error threshold. Nisheeth K. Vishnoi |
| 2013 | Massive online teaching to bounded learners. Brendan Juba, Ryan Williams |
| 2013 | Multiplicative updates in coordination games and the theory of evolution. Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani |
| 2013 | New affine-invariant codes from lifting. Alan Guo, Swastik Kopparty, Madhu Sudan |
| 2013 | On the convergence of the Hegselmann-Krause system. Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle, Huy L. Nguyen |
| 2013 | On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction. Boaz Barak, Guy Kindler, David Steurer |
| 2013 | On the possibilities and limitations of pseudodeterministic algorithms. Oded Goldreich, Shafi Goldwasser, Dana Ron |
| 2013 | On the power of conditional samples in distribution testing. Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah |
| 2013 | On the power of many one-bit provers. Per Austrin, Johan Håstad, Rafael Pass |
| 2013 | On the power of nonuniformity in proofs of security. Kai-Min Chung, Huijia Lin, Mohammad Mahmoody, Rafael Pass |
| 2013 | Parametric digital auctions. Pablo Daniel Azar, Silvio Micali |
| 2013 | Properties and applications of boolean function composition. Avishay Tal |
| 2013 | Pseudo-partitions, transversality and locality: a combinatorial characterization for the space measure in algebraic proof systems. Ilario Bonacina, Nicola Galesi |
| 2013 | Publicly verifiable proofs of sequential work. Mohammad Mahmoody, Tal Moran, Salil P. Vadhan |
| 2013 | Reachability in graph timelines. Jakub Lacki, Piotr Sankowski |
| 2013 | Resource-based corruptions and the combinatorics of hidden diversity. Juan A. Garay, David S. Johnson, Aggelos Kiayias, Moti Yung |
| 2013 | Robust optimization in the presence of uncertainty. Joachim M. Buhmann, Matús Mihalák, Rastislav Srámek, Peter Widmayer |
| 2013 | Runtime guarantees for regression problems. Hui Han Chin, Aleksander Madry, Gary L. Miller, Richard Peng |
| 2013 | Sorting noisy data with partial information. Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 2013 | Space-bounded communication complexity. Joshua Brody, Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, Xiaoming Sun |
| 2013 | Sparse extractor families for all the entropy. Andrej Bogdanov, Siyao Guo |
| 2013 | Streaming computations with a loquacious prover. Hartmut Klauck, Ved Prakash |
| 2013 | Stronger methods of making quantum interactive proofs perfectly complete. Hirotada Kobayashi, François Le Gall, Harumichi Nishimura |
| 2013 | The garden-hose model. Harry Buhrman, Serge Fehr, Christian Schaffner, Florian Speelman |
| 2013 | Time hierarchies for sampling distributions. Thomas Watson |
| 2013 | Towards an optimal query efficient PCP? Subhash Khot, Muli Safra, Madhur Tulsiani |
| 2013 | Welfare maximization and the supermodular degree. Uriel Feige, Rani Izsak |