| 2018 | (Gap/S)ETH hardness of SVP. Divesh Aggarwal, Noah Stephens-Davidowitz |
| 2018 | A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, Hang Zhou |
| 2018 | A PSPACE construction of a hitting set for the closure of small algebraic circuits. Michael A. Forbes, Amir Shpilka |
| 2018 | A constant-factor approximation algorithm for the asymmetric traveling salesman problem. Ola Svensson, Jakub Tarnawski, László A. Végh |
| 2018 | A converse to Banach's fixed point theorem and its CLS-completeness. Constantinos Daskalakis, Christos Tzamos, Manolis Zampetakis |
| 2018 | A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden |
| 2018 | A friendly smoothed analysis of the simplex method. Daniel Dadush, Sophie Huiberts |
| 2018 | A generalized Turán problem and its applications. Lior Gishboliner, Asaf Shapira |
| 2018 | A matrix expander Chernoff bound. Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava |
| 2018 | A simply exponential upper bound on the maximum number of stable matchings. Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber |
| 2018 | A tighter welfare guarantee for first-price auctions. Darrell Hoy, Samuel Taggart, Zihe Wang |
| 2018 | Algorithmic polynomials. Alexander A. Sherstov |
| 2018 | Almost polynomial hardness of node-disjoint paths in grids. Julia Chuzhoy, David H. K. Kim, Rachit Nimavat |
| 2018 | An almost-linear time algorithm for uniform random spanning tree generation. Aaron Schild |
| 2018 | An exponential lower bound for individualization-refinement algorithms for graph isomorphism. Daniel Neuen, Pascal Schweitzer |
| 2018 | An homotopy method for l Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li |
| 2018 | An optimal distributed (Δ+1)-coloring algorithm? Yi-Jun Chang, Wenzheng Li, Seth Pettie |
| 2018 | Approximating generalized network design under (dis)economies of scale with applications to energy efficiency. Yuval Emek, Shay Kutten, Ron Lavi, Yangguang Shi |
| 2018 | At the roots of dictionary compression: string attractors. Dominik Kempa, Nicola Prezza |
| 2018 | Bootstrapping variables in algebraic circuits. Manindra Agrawal, Sumanta Ghosh, Nitin Saxena |
| 2018 | Bounding the menu-size of approximately optimal auctions via optimal-transport duality. Yannai A. Gonczarowski |
| 2018 | Breaking the circuit-size barrier in secret sharing. Tianren Liu, Vinod Vaikuntanathan |
| 2018 | Capacity approaching coding for low noise interactive quantum communication. Debbie W. Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu |
| 2018 | Capacity upper bounds for deletion-type channels. Mahdi Cheraghchi |
| 2018 | Cell-probe lower bounds from online communication complexity. Josh Alman, Joshua R. Wang, Huacheng Yu |
| 2018 | Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. Cody Murray, R. Ryan Williams |
| 2018 | Clique is hard on average for regular resolution. Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov |
| 2018 | Collusion resistant traitor tracing from learning with errors. Rishab Goyal, Venkata Koppula, Brent Waters |
| 2018 | Composable and versatile privacy via truncated CDP. Mark Bun, Cynthia Dwork, Guy N. Rothblum, Thomas Steinke |
| 2018 | Consensus halving is PPA-complete. Aris Filos-Ratsikas, Paul W. Goldberg |
| 2018 | Constant approximation for k-median and k-means with outliers via iterative rounding. Ravishankar Krishnaswamy, Shi Li, Sai Sandeep |
| 2018 | Constant-factor approximation for ordered k-median. Jaroslaw Byrka, Krzysztof Sornat, Joachim Spoerhase |
| 2018 | Construction of new local spectral high dimensional expanders. Tali Kaufman, Izhar Oppenheim |
| 2018 | Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation. Yin Tat Lee, Santosh S. Vempala |
| 2018 | Counting hypergraph colourings in the local lemma regime. Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang |
| 2018 | Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. Kasper Green Larsen, Omri Weinstein, Huacheng Yu |
| 2018 | Data-dependent hashing via nonlinear spectral gaps. Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2018 | Deterministic distributed edge-coloring with fewer colors. Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara Uitto |
| 2018 | Discovering the roots: uniform closure results for algebraic classes under factoring. Pranjal Dutta, Nitin Saxena, Amit Sinhababu |
| 2018 | Distribution-free junta testing. Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie |
| 2018 | Dynamic matching in school choice: efficient seat reassignment after late cancellations (invited talk). Irene Lo |
| 2018 | Efficient decoding of random errors for quantum expander codes. Omar Fawzi, Antoine Grospellier, Anthony Leverrier |
| 2018 | Explicit binary tree codes with polylogarithmic size alphabet. Gil Cohen, Bernhard Haeupler, Leonard J. Schulman |
| 2018 | Extensor-coding. Cornelius Brand, Holger Dell, Thore Husfeldt |
| 2018 | Extractor-based time-space lower bounds for learning. Sumegha Garg, Ran Raz, Avishay Tal |
| 2018 | Fast algorithms for knapsack via convolution and prediction. MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, Cliff Stein |
| 2018 | Fast fencing. Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup |
| 2018 | Fine-grained complexity for sparse graphs. Udit Agarwal, Vijaya Ramachandran |
| 2018 | Fine-grained reductions from approximate counting to decision. Holger Dell, John Lapinskas |
| 2018 | Fully dynamic maximal independent set with sublinear update time. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon |
| 2018 | General strong polarization. Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan |
| 2018 | Generalization and equilibrium in generative adversarial nets (GANs) (invited talk). Tengyu Ma |
| 2018 | Generalized matrix completion and algebraic natural proofs. Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov |
| 2018 | Hardness of approximate nearest neighbor search. Aviad Rubinstein |
| 2018 | Hitting sets with near-optimal error for read-once branching programs. Mark Braverman, Gil Cohen, Sumegha Garg |
| 2018 | Holiest minimum-cost paths and flows in surface graphs. Jeff Erickson, Kyle Fox, Luvsandondov Lkhamsuren |
| 2018 | How to match when all vertices arrive online. Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, Xue Zhu |
| 2018 | Improved approximation for tree augmentation: saving by rewiring. Fabrizio Grandoni, Christos Kalaitzis, Rico Zenklusen |
| 2018 | Improved distributed algorithms for exact shortest paths. Mohsen Ghaffari, Jason Li |
| 2018 | Improved pseudorandomness for unordered branching programs through local monotonicity. Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal |
| 2018 | Inapproximability of the independent set polynomial in the complex plane. Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic |
| 2018 | Incomplete nested dissection. Rasmus Kyng, Richard Peng, Robert Schwieterman, Peng Zhang |
| 2018 | Interactive coding over the noisy broadcast channel. Klim Efremenko, Gillat Kol, Raghuvansh Saxena |
| 2018 | Interactive compression to external information. Mark Braverman, Gillat Kol |
| 2018 | Learning geometric concepts with nasty noise. Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |
| 2018 | Lifting nullstellensatz to monotone span programs over any field. Toniann Pitassi, Robert Robere |
| 2018 | List-decodable robust mean estimation and learning mixtures of spherical gaussians. Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |
| 2018 | Metric embedding via shortest path decompositions. Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman |
| 2018 | Mixture models, robustness, and sum of squares proofs. Samuel B. Hopkins, Jerry Li |
| 2018 | Monotone circuit lower bounds from resolution. Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov |
| 2018 | More consequences of falsifying SETH and the orthogonal vectors conjecture. Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof |
| 2018 | Multi-collision resistance: a paradigm for keyless hash functions. Nir Bitansky, Yael Tauman Kalai, Omer Paneth |
| 2018 | Near-optimal linear decision trees for k-SUM and related problems. Daniel M. Kane, Shachar Lovett, Shay Moran |
| 2018 | Nearly work-efficient parallel algorithm for digraph reachability. Jeremy T. Fineman |
| 2018 | New classes of distributed time complexity. Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela |
| 2018 | Non-malleable secret sharing. Vipul Goyal, Ashutosh Kumar |
| 2018 | Nonlinear dimension reduction via outer Bi-Lipschitz extensions. Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn |
| 2018 | On approximating the number of k-cliques in sublinear time. Talya Eden, Dana Ron, C. Seshadhri |
| 2018 | On non-optimally expanding sets in Grassmann graphs. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra |
| 2018 | On the complexity of hazard-free circuits. Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, Karteek Sreenivasaiah |
| 2018 | On the parameterized complexity of approximating dominating set. Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi |
| 2018 | Online load balancing on related machines. Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, Maryam Shadloo |
| 2018 | Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson |
| 2018 | Operator scaling with specified marginals. Cole Franks |
| 2018 | Prediction with a short memory. Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant |
| 2018 | Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 Ilias Diakonikolas, David Kempe, Monika Henzinger |
| 2018 | Quantified derandomization of linear threshold circuits. Roei Tell |
| 2018 | Robust moment estimation and improved clustering via sum of squares. Pravesh K. Kothari, Jacob Steinhardt, David Steurer |
| 2018 | Round compression for parallel matching algorithms. Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski |
| 2018 | Shadow tomography of quantum states. Scott Aaronson |
| 2018 | Shape of diffusion and size of monochromatic region of a two-dimensional spin system. Hamed Omidvar, Massimo Franceschetti |
| 2018 | Simulation beats richness: new data-structure lower bounds. Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay |
| 2018 | Smooth heaps and a dual view of self-adjusting data structures. László Kozma, Thatchaphol Saranurak |
| 2018 | Sparse Kneser graphs are Hamiltonian. Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak |
| 2018 | Stochastic bandits robust to adversarial corruptions. Thodoris Lykouris, Vahab S. Mirrokni, Renato Paes Leme |
| 2018 | Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev. Yin Tat Lee, Santosh S. Vempala |
| 2018 | Succinct delegation for low-space non-deterministic computation. Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs |
| 2018 | Sum-of-squares meets nash: lower bounds for finding any equilibrium. Pravesh K. Kothari, Ruta Mehta |
| 2018 | Synchronization strings: explicit constructions, local decoding, and applications. Bernhard Haeupler, Amirbehshad Shahrasbi |
| 2018 | Testing conditional independence of discrete distributions. Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |
| 2018 | The Paulsen problem, continuous operator scaling, and smoothed analysis. Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Akshay Ramachandran |
| 2018 | The adaptive complexity of maximizing a submodular function. Eric Balkanski, Yaron Singer |
| 2018 | The art gallery problem is ∃ ℝ-complete. Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow |
| 2018 | The gram-schmidt walk: a cure for the Banaszczyk blues. Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett |
| 2018 | The minimum euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential. Jesús A. De Loera, Jamie Haddock, Luis Rademacher |
| 2018 | The polynomial method strikes back: tight quantum query bounds via dual polynomials. Mark Bun, Robin Kothari, Justin Thaler |
| 2018 | The query complexity of graph isomorphism: bypassing distribution testing lower bounds. Krzysztof Onak, Xiaorui Sun |
| 2018 | Tight cell probe bounds for succinct Boolean matrix-vector multiplication. Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen |
| 2018 | Tight query complexity lower bounds for PCA via finite sample deformed wigner law. Max Simchowitz, Ahmed El Alaoui, Benjamin Recht |
| 2018 | Towards a proof of the 2-to-1 games conjecture? Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra |
| 2018 | Towards tight approximation bounds for graph diameter and eccentricities. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein |
| 2018 | Universal points in the asymptotic spectrum of tensors. Matthias Christandl, Péter Vrana, Jeroen Zuiddam |
| 2018 | Universal protocols for information dissemination using emergent signals. Bartlomiej Dudek, Adrian Kosowski |
| 2018 | k-server via multiscale entropic regularization. Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, Aleksander Madry |