| 2018 | 0/1/All CSPs, Half-Integral A-Path Packing, and Linear-Time FPT Algorithms. Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida |
| 2018 | 1-Factorizations of Pseudorandom Graphs. Asaf Ferber, Vishesh Jain |
| 2018 | 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018 Mikkel Thorup |
| 2018 | A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick |
| 2018 | A Faster Distributed Single-Source Shortest Paths Algorithm. Sebastian Forster, Danupon Nanongkai |
| 2018 | A Faster Isomorphism Test for Graphs of Small Degree. Martin Grohe, Daniel Neuen, Pascal Schweitzer |
| 2018 | A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees. Rasmus Kyng, Zhao Song |
| 2018 | A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan |
| 2018 | A Short List of Equalities Induces Large Sign Rank. Arkadev Chattopadhyay, Nikhil S. Mande |
| 2018 | An ETH-Tight Exact Algorithm for Euclidean TSP. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Sudeshna Kolay |
| 2018 | An End-to-End Argument in Mechanism Design (Prior-Independent Auctions for Budgeted Agents). Yiding Feng, Jason D. Hartline |
| 2018 | An Improved Bound for Weak Epsilon-Nets in the Plane. Natan Rubin |
| 2018 | Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks |
| 2018 | Approximating the Permanent of a Random Matrix with Vanishing Mean. Lior Eldar, Saeed Mehraban |
| 2018 | Balancing Vectors in Any Norm. Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, Nicole Tomczak-Jaegermann |
| 2018 | Beating the Integrality Ratio for s-t-Tours in Graphs. Vera Traub, Jens Vygen |
| 2018 | Bloom Filters, Adaptivity, and the Dictionary Problem. Michael A. Bender, Martin Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, Shikha Singh |
| 2018 | Classical Homomorphic Encryption for Quantum Circuits. Urmila Mahadev |
| 2018 | Classical Lower Bounds from Quantum Upper Bounds. Shalev Ben-David, Adam Bouland, Ankit Garg, Robin Kothari |
| 2018 | Classical Verification of Quantum Computations. Urmila Mahadev |
| 2018 | Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols. Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak |
| 2018 | Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time. Jatin Batra, Naveen Garg, Amit Kumar |
| 2018 | Constant Overhead Quantum Fault-Tolerance with Quantum Expander Codes. Omar Fawzi, Antoine Grospellier, Anthony Leverrier |
| 2018 | Contextual Search via Intrinsic Volumes. Renato Paes Leme, Jon Schneider |
| 2018 | Coordinate Methods for Accelerating ℓ∞ Regression and Faster Approximate Maximum Flow. Aaron Sidford, Kevin Tian |
| 2018 | Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems. Oded Goldreich, Guy N. Rothblum |
| 2018 | Cryptographic Hashing from Strong One-Way Functions (Or: One-Way Product Functions and Their Applications). Justin Holmgren, Alex Lombardi |
| 2018 | Delegating Computations with (Almost) Minimal Time and Space Overhead. Justin Holmgren, Ron Rothblum |
| 2018 | Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors. Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu |
| 2018 | Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich |
| 2018 | Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization. Maria-Florina Balcan, Travis Dick, Ellen Vitercik |
| 2018 | EPTAS for Max Clique on Disks and Unit Balls. Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé |
| 2018 | Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson |
| 2018 | Efficient Density Evaluation for Smooth Kernels. Arturs Backurs, Moses Charikar, Piotr Indyk, Paris Siminelakis |
| 2018 | Efficient Polynomial-Time Approximation Scheme for the Genus of Dense Graphs. Bojan Mohar, Yifan Jing |
| 2018 | Efficient Statistics, in High Dimensions, from Truncated Samples. Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Manolis Zampetakis |
| 2018 | Efficiently Learning Mixtures of Mallows Models. Allen Liu, Ankur Moitra |
| 2018 | Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, Xuan Wu |
| 2018 | Faster Exact and Approximate Algorithms for k-Cut. Anupam Gupta, Euiwoong Lee, Jason Li |
| 2018 | Finding Forbidden Minors in Sublinear Time: A n^1/2+o(1)-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs. Akash Kumar, C. Seshadhri, Andrew Stolman |
| 2018 | Fusible HSTs and the Randomized k-Server Conjecture. James R. Lee |
| 2018 | Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm. Matthew Fahrbach, Gary L. Miller, Richard Peng, Saurabh Sawlani, Junxing Wang, Shen Chen Xu |
| 2018 | Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions. Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang |
| 2018 | Hardness Magnification for Natural Problems. Igor Carboni Oliveira, Rahul Santhanam |
| 2018 | Hölder Homeomorphisms and Approximate Nearest Neighbors. Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2018 | Improved Decoding of Folded Reed-Solomon and Multiplicity Codes. Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters |
| 2018 | Improved Online Algorithm for Weighted Flow Time. Yossi Azar, Noam Touitou |
| 2018 | Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs. Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola |
| 2018 | Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs. Johan Håstad |
| 2018 | Laconic Function Evaluation and Applications. Willy Quach, Hoeteck Wee, Daniel Wichs |
| 2018 | Learning Sums of Independent Random Variables with Sparse Collective Support. Anindya De, Philip M. Long, Rocco A. Servedio |
| 2018 | Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. Josh Alman, Virginia Vassilevska Williams |
| 2018 | Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids. Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant |
| 2018 | Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. Anand Natarajan, Thomas Vidick |
| 2018 | MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture. Shachar Lovett |
| 2018 | Metric Sublinear Algorithms via Linear Sampling. Hossein Esfandiari, Michael Mitzenmacher |
| 2018 | Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences. Mert Saglam |
| 2018 | Near-Optimal Approximate Decremental All Pairs Shortest Paths. Shiri Chechik |
| 2018 | Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. Mika Göös, Aviad Rubinstein |
| 2018 | Non-Black-Box Worst-Case to Average-Case Reductions within NP. Shuichi Hirahara |
| 2018 | Non-Malleable Codes for Small-Depth Circuits. Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan |
| 2018 | On Derandomizing Local Distributed Algorithms. Mohsen Ghaffari, David G. Harris, Fabian Kuhn |
| 2018 | On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs. Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk |
| 2018 | PPP-Completeness with Connections to Cryptography. Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis |
| 2018 | PanORAMa: Oblivious RAM with Logarithmic Overhead. Sarvar Patel, Giuseppe Persiano, Mariana Raykova, Kevin Yeo |
| 2018 | Parallel Graph Connectivity in Log Diameter Rounds. Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong |
| 2018 | Perfect Lp Sampling in a Data Stream. Rajesh Jayaram, David P. Woodruff |
| 2018 | Planar Graph Perfect Matching Is in NC. Nima Anari, Vijay V. Vazirani |
| 2018 | Privacy Amplification by Iteration. Vitaly Feldman, Ilya Mironov, Kunal Talwar, Abhradeep Thakurta |
| 2018 | Pseudorandom Generators for Read-Once Branching Programs, in Any Order. Michael A. Forbes, Zander Kelley |
| 2018 | Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion. Subhash Khot, Dor Minzer, Muli Safra |
| 2018 | Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians. Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low |
| 2018 | Random Order Contention Resolution Schemes. Marek Adamczyk, Michal Wlodarczyk |
| 2018 | Recharging Bandits. Robert Kleinberg, Nicole Immorlica |
| 2018 | Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation. Christian Borgs, Jennifer T. Chayes, Adam D. Smith, Ilias Zadik |
| 2018 | Simple Optimal Hitting Sets for Small-Success RL. William Hoza, David Zuckerman |
| 2018 | Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford |
| 2018 | Spatial Isolation Implies Zero Knowledge Even in a Quantum World. Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner |
| 2018 | Spectral Subspace Sparsification. Huan Li, Aaron Schild |
| 2018 | Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. Christian Sohler, David P. Woodruff |
| 2018 | Sublinear Algorithms for Local Graph Centrality Estimation. Marco Bressan, Enoch Peserico, Luca Pretto |
| 2018 | Testing Graph Clusterability: Algorithms and Lower Bounds. Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, Yuval Peres |
| 2018 | The Complexity of General-Valued CSPs Seen from the Other Side. Clément Carbonnel, Miguel Romero, Stanislav Zivný |
| 2018 | The Diameter of the Fractional Matching Polytope and Its Hardness Implications. Laura Sanità |
| 2018 | The Sample Complexity of Up-to-ε Multi-Dimensional Revenue Maximization. Yannai A. Gonczarowski, S. Matthew Weinberg |
| 2018 | The Sketching Complexity of Graph and Hypergraph Counting. John Kallaugher, Michael Kapralov, Eric Price |
| 2018 | Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling. Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri |
| 2018 | Towards Learning Sparsely Used Dictionaries with Arbitrary Supports. Pranjal Awasthi, Aravindan Vijayaraghavan |