| 2017 | A generalization of permanent inequalities and applications in counting and optimization. Nima Anari, Shayan Oveis Gharan |
| 2017 | A polynomial restriction lemma with applications. Valentine Kabanets, Daniel M. Kane, Zhenjian Lu |
| 2017 | A quantum linearity test for robustly verifying entanglement. Anand Natarajan, Thomas Vidick |
| 2017 | A reverse Minkowski theorem. Oded Regev, Noah Stephens-Davidowitz |
| 2017 | A simpler and faster strongly polynomial algorithm for generalized flow maximization. Neil Olver, László A. Végh |
| 2017 | A strongly polynomial algorithm for bimodular integer linear programming. Stephan Artmann, Robert Weismantel, Rico Zenklusen |
| 2017 | A time- and message-optimal distributed algorithm for minimum spanning trees. Gopal Pandurangan, Peter Robinson, Michele Scquizzato |
| 2017 | A weighted linear matroid parity algorithm. Satoru Iwata, Yusuke Kobayashi |
| 2017 | Addition is exponentially harder than counting for shallow monotone circuits. Xi Chen, Igor C. Oliveira, Rocco A. Servedio |
| 2017 | Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson |
| 2017 | Algorithmic discrepancy beyond partial coloring. Nikhil Bansal, Shashwat Garg |
| 2017 | Algorithms for stable and perturbation-resilient problems. Haris Angelidakis, Konstantin Makarychev, Yury Makarychev |
| 2017 | Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu |
| 2017 | Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. Pasin Manurangsi |
| 2017 | An SDP-based algorithm for linear-sized spectral sparsification. Yin Tat Lee, He Sun |
| 2017 | An adaptive sublinear-time block sparse fourier transform. Volkan Cevher, Michael Kapralov, Jonathan Scarlett, Amir Zandieh |
| 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 | Answering FAQs in CSPs, probabilistic graphical models, databases, logic and matrix operations (invited talk). Atri Rudra |
| 2017 | Approximate counting, the Lovasz local lemma, and inference in graphical models. Ankur Moitra |
| 2017 | Approximate modularity revisited. Uriel Feige, Michal Feldman, Inbal Talgam-Cohen |
| 2017 | Approximate near neighbors for general symmetric norms. Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2017 | Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra |
| 2017 | Area-convexity, l Jonah Sherman |
| 2017 | Average-case fine-grained hardness. Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan |
| 2017 | Beating 1-1/e for ordered prophets. Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Robert D. Kleinberg, Brendan Lucier |
| 2017 | Bernoulli factories and black-box reductions in mechanism design. Shaddin Dughmi, Jason D. Hartline, Robert Kleinberg, Rad Niazadeh |
| 2017 | Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. Xi Chen, Erik Waingarten, Jinyu Xie |
| 2017 | Communication complexity of approximate Nash equilibria. Yakov Babichenko, Aviad Rubinstein |
| 2017 | Complexity of short Presburger arithmetic. Danny Nguyen, Igor Pak |
| 2017 | Compression of quantum multi-prover interactive proofs. Zhengfeng Ji |
| 2017 | Deciding parity games in quasipolynomial time. Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan |
| 2017 | DecreaseKeys are expensive for external memory priority queues. Kasper Eenberg, Kasper Green Larsen, Huacheng Yu |
| 2017 | Decremental single-source reachability in planar digraphs. Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Piotr Sankowski |
| 2017 | Distributed exact shortest paths in sublinear time. Michael Elkin |
| 2017 | Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n Danupon Nanongkai, Thatchaphol Saranurak |
| 2017 | Efficient empirical revenue maximization in single-parameter auction environments. Yannai A. Gonczarowski, Noam Nisan |
| 2017 | Efficient massively parallel methods for dynamic programming. Sungjin Im, Benjamin Moseley, Xiaorui Sun |
| 2017 | Efficient quantum tomography II. Ryan O'Donnell, John Wright |
| 2017 | Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model. Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam |
| 2017 | Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk). Orna Kupferman |
| 2017 | Explicit, almost optimal, epsilon-balanced codes. Amnon Ta-Shma |
| 2017 | Exponential separation of quantum communication and classical information. Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu |
| 2017 | Exponential separations in the energy complexity of leader election. Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan |
| 2017 | Fast convergence of learning in games (invited talk). Vasilis Syrgkanis |
| 2017 | Faster space-efficient algorithms for subset sum and k-sum. Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas |
| 2017 | Finding approximate local minima faster than gradient descent. Naman Agarwal, Zeyuan Allen Zhu, Brian Bullins, Elad Hazan, Tengyu Ma |
| 2017 | Finding even cycles faster via capped k-walks. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel |
| 2017 | Formula lower bounds via the quantum method. Avishay Tal |
| 2017 | Fully-dynamic minimum spanning forest with improved worst-case update time. Christian Wulff-Nilsen |
| 2017 | Geodesic walks in polytopes. Yin Tat Lee, Santosh S. Vempala |
| 2017 | Hardness amplification for entangled games via anchoring. Mohammad Bavarian, Thomas Vidick, Henry Yuen |
| 2017 | Holographic algorithm with matchgates is universal for planar #CSP over boolean domain. Jin-Yi Cai, Zhiguo Fu |
| 2017 | Homomorphisms are a good basis for counting small subgraphs. Radu Curticapean, Holger Dell, Dániel Marx |
| 2017 | How well do local algorithms solve semidefinite programs? Zhou Fan, Andrea Montanari |
| 2017 | Improved non-malleable extractors, non-malleable codes and independent source extractors. Xin Li |
| 2017 | Information-theoretic thresholds from the cavity method. Amin Coja-Oghlan, Florent Krzakala, Will Perkins, Lenka Zdeborová |
| 2017 | Katyusha: the first direct acceleration of stochastic gradient methods. Zeyuan Allen Zhu |
| 2017 | Kernel-based methods for bandit convex optimization. Sébastien Bubeck, Yin Tat Lee, Ronen Eldan |
| 2017 | Kolmogorov complexity version of Slepian-Wolf coding. Marius Zimand |
| 2017 | Learning from untrusted data. Moses Charikar, Jacob Steinhardt, Gregory Valiant |
| 2017 | Linear matroid intersection is in quasi-NC. Rohit Gurjar, Thomas Thierauf |
| 2017 | Local max-cut in smoothed polynomial time. Omer Angel, Sébastien Bubeck, Yuval Peres, Fan Wei |
| 2017 | Lossy kernelization. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh |
| 2017 | Low rank approximation with entrywise l Zhao Song, David P. Woodruff, Peilin Zhong |
| 2017 | New hardness results for routing on disjoint paths. Julia Chuzhoy, David H. K. Kim, Rachit Nimavat |
| 2017 | Non-interactive delegation and batch NP verification from standard computational assumptions. Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai |
| 2017 | Non-malleable codes and extractors for small-depth circuits, and affine functions. Eshan Chattopadhyay, Xin Li |
| 2017 | On independent sets, 2-to-2 games, and Grassmann graphs. Subhash Khot, Dor Minzer, Muli Safra |
| 2017 | On the complexity of local distributed graph problems. Mohsen Ghaffari, Fabian Kuhn, Yannic Maus |
| 2017 | Online and dynamic algorithms for set cover. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi |
| 2017 | Online service with delay. Yossi Azar, Arun Ganesh, Rong Ge, Debmalya Panigrahi |
| 2017 | Optimal mean-based algorithms for trace reconstruction. Anindya De, Ryan O'Donnell, Rocco A. Servedio |
| 2017 | Optimizing tree pattern queries: why cutting is not enough (invited talk). Wim Martens |
| 2017 | Practical post-quantum key agreement from generic lattices (invited talk). Valeria Nikolaenko |
| 2017 | Probabilistic rank and matrix rigidity. Josh Alman, R. Ryan Williams |
| 2017 | Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 Hamed Hatami, Pierre McKenzie, Valerie King |
| 2017 | Provable learning of noisy-OR networks. Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski |
| 2017 | Pseudodeterministic constructions in subexponential time. Igor C. Oliveira, Rahul Santhanam |
| 2017 | Pseudorandomness of ring-LWE for any ring and modulus. Chris Peikert, Oded Regev, Noah Stephens-Davidowitz |
| 2017 | Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. Andris Ambainis, Martins Kokainis |
| 2017 | Quantum entanglement, sum of squares, and the log rank conjecture. Boaz Barak, Pravesh K. Kothari, David Steurer |
| 2017 | Randomized polynomial time identity testing for noncommutative circuits. Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, S. Raja |
| 2017 | Real stable polynomials and matroids: optimization and counting. Damian Straszak, Nisheeth K. Vishnoi |
| 2017 | Recent trends in decentralized cryptocurrencies (invited talk). Aviv Zohar |
| 2017 | Removal lemmas with polynomial bounds. Lior Gishboliner, Asaf Shapira |
| 2017 | Sampling random spanning trees faster than matrix multiplication. David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva |
| 2017 | Set similarity search beyond MinHash. Tobias Christiani, Rasmus Pagh |
| 2017 | Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod |
| 2017 | Simple mechanisms for subadditive buyers via duality. Yang Cai, Mingfei Zhao |
| 2017 | Stability of service under time-of-use pricing. Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, Balasubramanian Sivan |
| 2017 | Streaming symmetric norms via measure concentration. Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang |
| 2017 | Strongly exponential lower bounds for monotone computation. Toniann Pitassi, Robert Robere |
| 2017 | Strongly refuting random CSPs below the spectral threshold. Prasad Raghavendra, Satish Rao, Tselil Schramm |
| 2017 | Subquadratic submodular function minimization. Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong |
| 2017 | Succinct hitting sets and barriers to proving algebraic circuits lower bounds. Michael A. Forbes, Amir Shpilka, Ben Lee Volk |
| 2017 | Sum of squares lower bounds for refuting any CSP. Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer |
| 2017 | Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree. Fabrizio Grandoni, Bundit Laekhanukit |
| 2017 | Synchronization strings: codes for insertions and deletions approaching the Singleton bound. Bernhard Haeupler, Amirbehshad Shahrasbi |
| 2017 | Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. William M. Hoza, Chris Umans |
| 2017 | The computational complexity of ball permutations. Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban |
| 2017 | The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n. Assaf Naor, Robert Young |
| 2017 | The limitations of optimization from samples. Eric Balkanski, Aviad Rubinstein, Yaron Singer |
| 2017 | The menu-size complexity of revenue approximation. Moshe Babaioff, Yannai A. Gonczarowski, Noam Nisan |
| 2017 | The next 700 network programming languages (invited talk). Nate Foster |
| 2017 | The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation. Pierre-Étienne Meunier, Damien Woods |
| 2017 | Time-space hardness of learning sparse parities. Gillat Kol, Ran Raz, Avishay Tal |
| 2017 | Towards optimal two-source extractors and Ramsey graphs. Gil Cohen |
| 2017 | Trace reconstruction with exp(O(n Fedor Nazarov, Yuval Peres |
| 2017 | Twenty (simple) questions. Yuval Dagan, Yuval Filmus, Ariel Gabizon, Shay Moran |
| 2017 | Uniform sampling through the Lovasz local lemma. Heng Guo, Mark Jerrum, Jingcheng Liu |
| 2017 | Why prices need algorithms (invited talk). Tim Roughgarden, Inbal Talgam-Cohen |