| 2017 | Exponential separations in the energy complexity of leader election. | Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan |
| 2017 | Subquadratic submodular function minimization. | Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong |
| 2017 | An adaptive sublinear-time block sparse fourier transform. | Volkan Cevher, Michael Kapralov, Jonathan Scarlett, Amir Zandieh |
| 2017 | Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model. | Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam |
| 2017 | Deciding parity games in quasipolynomial time. | Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan |
| 2017 | Simple mechanisms for subadditive buyers via duality. | Yang Cai, Mingfei Zhao |
| 2017 | Holographic algorithm with matchgates is universal for planar #CSP over boolean domain. | Jin-Yi Cai, Zhiguo Fu |
| 2017 | Kernel-based methods for bandit convex optimization. | Sbastien Bubeck, Yin Tat Lee, Ronen Eldan |
| 2017 | Non-interactive delegation and batch NP verification from standard computational assumptions. | Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai |
| 2017 | Streaming symmetric norms via measure concentration. | Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang |
| 2017 | An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy. | Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma |
| 2017 | Hardness amplification for entangled games via anchoring. | Mohammad Bavarian, Thomas Vidick, Henry Yuen |
| 2017 | Quantum entanglement, sum of squares, and the log rank conjecture. | Boaz Barak, Pravesh K. Kothari, David Steurer |
| 2017 | Faster space-efficient algorithms for subset sum and k-sum. | Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas |
| 2017 | Algorithmic discrepancy beyond partial coloring. | Nikhil Bansal, Shashwat Garg |
| 2017 | Average-case fine-grained hardness. | Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan |
| 2017 | The limitations of optimization from samples. | Eric Balkanski, Aviad Rubinstein, Yaron Singer |
| 2017 | Communication complexity of approximate Nash equilibria. | Yakov Babichenko, Aviad Rubinstein |
| 2017 | The menu-size complexity of revenue approximation. | Moshe Babaioff, Yannai A. Gonczarowski, Noam Nisan |
| 2017 | Online service with delay. | Yossi Azar, Arun Ganesh, Rong Ge, Debmalya Panigrahi |
| 2017 | Randomized polynomial time identity testing for noncommutative circuits. | Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, S. Raja |
| 2017 | A strongly polynomial algorithm for bimodular integer linear programming. | Stephan Artmann, Robert Weismantel, Rico Zenklusen |
| 2017 | Provable learning of noisy-OR networks. | Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski |
| 2017 | Exponential separation of quantum communication and classical information. | Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu |
| 2017 | Algorithms for stable and perturbation-resilient problems. | Haris Angelidakis, Konstantin Makarychev, Yury Makarychev |