| 2018 | A Hadley Black, Deeparnab Chakrabarty, C. Seshadhri |
| 2018 | A Fast Approximation Scheme for Low-Dimensional Vincent Cohen-Addad |
| 2018 | A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs. Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, Sharath Raghvendra |
| 2018 | A Framework for the Secretary Problem on the Intersection of Matroids. Moran Feldman, Ola Svensson, Rico Zenklusen |
| 2018 | A Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problem. Sharath Raghvendra, Mariëtte C. Wessels |
| 2018 | A Hamilton Path for the Sigma-Tau Problem. Joe Sawada, Aaron Williams |
| 2018 | A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time. Stephen Alstrup, Agelos Georgakopoulos, Eva Rotenberg, Carsten Thomassen |
| 2018 | A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals. Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay |
| 2018 | A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth. Mateus de Oliveira Oliveira |
| 2018 | A Nearly Instance Optimal Algorithm for Top- Xi Chen, Yuanzhi Li, Jieming Mao |
| 2018 | A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications. Nikhil R. Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod |
| 2018 | A Polynomial Excluded-Minor Approximation of Treedepth. Ken-ichi Kawarabayashi, Benjamin Rossman |
| 2018 | A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank. Radu Curticapean, Nathan Lindzey, Jesper Nederlof |
| 2018 | A Two-pronged Progress in Structured Dense Matrix Vector Multiplication. Christopher De Sa, Albert Gu, Rohan Puttagunta, Christopher Ré, Atri Rudra |
| 2018 | A fast generalized DFT for finite groups of Lie type. Chloe Ching-Yun Hsu, Chris Umans |
| 2018 | A submodular measure and approximate Gomory-Hu theorem for packing odd trails. Ross Churchley, Bojan Mohar |
| 2018 | A tight -approximation for Linear 3-Cut. Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Vivek Madan |
| 2018 | Adaptive Hierarchical Clustering Using Ordinal Queries. Ehsan Emamjomeh-Zadeh, David Kempe |
| 2018 | Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing. Gábor Ivanyos, Youming Qiao |
| 2018 | Algorithms to Approximate Column-Sparse Packing Problems. Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, Pan Xu |
| 2018 | Almost Envy-Freeness with General Valuations. Benjamin Plaut, Tim Roughgarden |
| 2018 | An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification. Nikhil Srivastava, Luca Trevisan |
| 2018 | An FPT Algorithm Beating 2-Approximation for Anupam Gupta, Euiwoong Lee, Jason Li |
| 2018 | Approaching for the Vera Traub, Jens Vygen |
| 2018 | Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius. Pooya Hatami, Madhur Tulsiani |
| 2018 | Approximate Positive Correlated Distributions and Approximation Algorithms for D-optimal Design. Mohit Singh, Weijun Xie |
| 2018 | Approximate Single Source Fault Tolerant Shortest Path. Surender Baswana, Keerti Choudhary, Moazzam Hussain, Liam Roditty |
| 2018 | Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners. Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, Virginia Vassilevska Williams |
| 2018 | Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce. Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Saeed Seddighin |
| 2018 | Approximating Weighted Tree Augmentation via Chvátal-Gomory Cuts. Samuel Fiorini, Martin Groß, Jochen Könemann, Laura Sanità |
| 2018 | Approximating the Largest Root and Applications to Interlacing Families. Nima Anari, Shayan Oveis Gharan, Amin Saberi, Nikhil Srivastava |
| 2018 | Approximating the Nash Social Welfare with Budget-Additive Valuations. Jugal Garg, Martin Hoefer, Kurt Mehlhorn |
| 2018 | Approximation Schemes for Clustering with Outliers. Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, Mohammad R. Salavatipour |
| 2018 | Average-radius list-recoverability of random linear codes. Atri Rudra, Mary Wootters |
| 2018 | Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth. Daniel Lokshtanov, Ivan Mikhailin, Ramamohan Paturi, Pavel Pudlák |
| 2018 | Better Tradeoffs for Exact Distance Oracles in Planar Graphs. Pawel Gawrychowski, Shay Mozes, Oren Weimann, Christian Wulff-Nilsen |
| 2018 | Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack. Anindya De |
| 2018 | Cache-Oblivious and Data-Oblivious Sorting and Applications. T.-H. Hubert Chan, Yue Guo, Wei-Kai Lin, Elaine Shi |
| 2018 | Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi |
| 2018 | Coding against deletions in oblivious and online models. Venkatesan Guruswami, Ray Li |
| 2018 | Community Detection on Euclidean Random Graphs. Abishek Sankararaman, François Baccelli |
| 2018 | Comparing mixing times on sparse random graphs. Anna Ben-Hamou, Eyal Lubetzky, Yuval Peres |
| 2018 | Competitive Algorithms for Generalized Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, Jesper Nederlof |
| 2018 | Computing Simplicial Representatives of Homotopy Group Elements. Marek Filakovský, Peter Franek, Uli Wagner, Stephan Zhechev |
| 2018 | Computing the Independence Polynomial: from the Tree Threshold down to the Roots. Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák |
| 2018 | Conflict-Free Coloring of Intersection Graphs of Geometric Objects. Chaya Keller, Shakhar Smorodinsky |
| 2018 | Consensus of Interacting Particle Systems on Erdös-Rényi Graphs. Grant Schoenebeck, Fang-Yi Yu |
| 2018 | Consistent Hashing with Bounded Loads. Vahab S. Mirrokni, Mikkel Thorup, Morteza Zadimoghaddam |
| 2018 | Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Meirav Zehavi |
| 2018 | Covering a tree with rooted subtrees - parameterized and approximation algorithms. Lin Chen, Dániel Marx |
| 2018 | Cycles in Adversarial Regularized Learning. Panayotis Mertikopoulos, Christos H. Papadimitriou, Georgios Piliouras |
| 2018 | Decrementai Transitive Closure and Shortest Paths for Planar Digraphs and Beyond. Adam Karczmarz |
| 2018 | Derandomized concentration bounds for polynomials, and hypergraph maximal independent set. David G. Harris |
| 2018 | Dichotomy for Real Holant Jin-Yi Cai, Pinyan Lu, Mingji Xia |
| 2018 | Discrete Choice, Permutations, and Reconstruction. Flavio Chierichetti, Ravi Kumar, Andrew Tomkins |
| 2018 | Dynamic Algorithms for Graph Coloring. Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, Danupon Nanongkai |
| 2018 | Dynamic Bridge-Finding in Jacob Holm, Eva Rotenberg, Mikkel Thorup |
| 2018 | Efficient Arun Jambulapati, Aaron Sidford |
| 2018 | Embeddability in ℝ Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick, Martin Tancer |
| 2018 | Envy-free Chore Division for An Arbitrary Number of Agents. Sina Dehghani, Alireza Farhadi, Mohammad Taghi Hajiaghayi, Hadi Yami |
| 2018 | Erdős-Pósa property of chordless cycles and its applications. Eun Jung Kim, O-joung Kwon |
| 2018 | Ergodic Effects in Token Circulation. Adrian Kosowski, Przemyslaw Uznanski |
| 2018 | Estimating Graph Parameters from Random Order Streams. Pan Peng, Christian Sohler |
| 2018 | Estimating graph parameters via random walks with restarts. Anna Ben-Hamou, Roberto I. Oliveira, Yuval Peres |
| 2018 | Exponentially slow mixing in the mean-field Swendsen-Wang dynamics. Reza Gheissari, Eyal Lubetzky, Yuval Peres |
| 2018 | Fast Space Optimal Leader Election in Population Protocols. Leszek Gasieniec, Grzegorz Stachowiak |
| 2018 | Fast, Deterministic and Sparse Dimensionality Reduction. Daniel Dadush, Cristóbal Guzmán, Neil Olver |
| 2018 | From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games. Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin, Philip B. Stark |
| 2018 | Front Matter. |
| 2018 | Fréchet-Stable Signatures Using Persistence Homology. Donald R. Sheehy |
| 2018 | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. David Coudert, Guillaume Ducoffe, Alexandru Popa |
| 2018 | Geometric Rescaling Algorithms for Submodular Function Minimization. Daniel Dadush, László A. Végh, Giacomo Zambelli |
| 2018 | Hierarchical Clustering: Objective Functions and Algorithms. Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu |
| 2018 | Hypergraph Karthekeyan Chandrasekaran, Chao Xu, Xilin Yu |
| 2018 | Impossibility of dimension reduction in the nuclear norm. Assaf Naor, Gilles Pisier, Gideon Schechtman |
| 2018 | Improved Bounds for Testing Forbidden Order Patterns. Omri Ben-Eliezer, Clément L. Canonne |
| 2018 | Improved Coresets for Kernel Density Estimates. Jeff M. Phillips, Wai Ming Tai |
| 2018 | Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. Francois Le Gall, Florent Urrutia |
| 2018 | Improved bounds for testing Dyck languages. Eldar Fischer, Frédéric Magniez, Tatiana Starikovskaya |
| 2018 | In-Place Sparse Suffix Sorting. Nicola Prezza |
| 2018 | Incremental DFS algorithms: a theoretical and experimental study. Surender Baswana, Ayush Goel, Shahbaz Khan |
| 2018 | Incremental Topological Sort and Cycle Detection in Expected Total Time. Aaron Bernstein, Shiri Chechik |
| 2018 | Kirchhoff Index as a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms. Huan Li, Zhongzhi Zhang |
| 2018 | Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees. Pawel Gawrychowski, Fabian Kuhn, Jakub Lopuszanski, Konstantinos Panagiotou, Pascal Su |
| 2018 | Lempel-Ziv: a "one-bit catastrophe" but not a tragedy. Guillaume Lagarde, Sylvain Perifel |
| 2018 | Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting. Alfonso Cevallos, Stefan Weltge, Rico Zenklusen |
| 2018 | Localization of Electrical Flows. Aaron Schild, Satish Rao, Nikhil Srivastava |
| 2018 | Lower Bounds for Approximating the Matching Polytope. Makrand Sinha |
| 2018 | Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter. Krishnendu Chatterjee, Wolfgang Dvorák, Monika Henzinger, Veronika Loitzenbauer |
| 2018 | MST in Tomasz Jurdzinski, Krzysztof Nowicki |
| 2018 | Metric Violation Distance: Hardness and Approximation. Chenglin Fan, Benjamin Raichel, Gregory Van Buskirk |
| 2018 | Minimum Cut of Directed Planar Graphs in Shay Mozes, Kirill Nikolaev, Yahav Nussbaum, Oren Weimann |
| 2018 | Minor-matching hypertree width. Nikola Yolov |
| 2018 | More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems. Timothy M. Chan |
| 2018 | Multivariate Fine-Grained Complexity of Longest Common Subsequence. Karl Bringmann, Marvin Künnemann |
| 2018 | Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. Nima Anari, Tung Mai, Shayan Oveis Gharan, Vijay V. Vazirani |
| 2018 | Near Optimal Jointly Private Packing Algorithms via Dual Multiplicative Weight Update. Zhiyi Huang, Xue Zhu |
| 2018 | Near-Optimal Compression for the Planar Graph Metric. Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2018 | Near-optimal approximation algorithm for simultaneous Max-Cut. Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva, Devanathan Thiruvenkatachari |
| 2018 | Nearly Tight Bounds for Sandpile Transience on the Grid. David Durfee, Matthew Fahrbach, Yu Gao, Tao Xiao |
| 2018 | Nested Convex Bodies are Chaseable. Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, Seeun William Umboh |
| 2018 | Non interactive simulation of correlated distributions is decidable. Anindya De, Elchanan Mossel, Joe Neeman |
| 2018 | On Separating Points by Lines. Sariel Har-Peled, Mitchell Jones |
| 2018 | On Simultaneous Two-player Combinatorial Auctions. Mark Braverman, Jieming Mao, S. Matthew Weinberg |
| 2018 | On the Competition Complexity of Dynamic Mechanism Design. Siqi Liu, Christos-Alexandros Psomas |
| 2018 | On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer. Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis |
| 2018 | On the Decidability of the Fréchet Distance between Surfaces. Amir Nayyeri, Hanzhong Xu |
| 2018 | On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity. Ryan Williams |
| 2018 | On the complexity of optimal homotopies. Erin Wolf Chambers, Arnaud de Mesmay, Tim Ophelders |
| 2018 | On the complexity of range searching among curves. Peyman Afshani, Anne Driemel |
| 2018 | Online Bipartite Matching with Amortized Replacements. Aaron Bernstein, Jacob Holm, Eva Rotenberg |
| 2018 | Online Facility Location against a Harry Lang |
| 2018 | Optimal Dynamic Strings. Pawel Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Lacki, Piotr Sankowski |
| 2018 | Optimal Vertex Fault Tolerant Spanners (for fixed stretch). Greg Bodwin, Michael Dinitz, Merav Parter, Virginia Vassilevska Williams |
| 2018 | Optimal streaming and tracking distinct elements with high probability. Jaroslaw Blasiok |
| 2018 | Optimal-Time Text Indexing in BWT-runs Bounded Space. Travis Gagie, Gonzalo Navarro, Nicola Prezza |
| 2018 | Parameterized Algorithms for Survivable Network Design with Uniform Demands. Jørgen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi |
| 2018 | Persistent Path Homology of Directed Networks. Samir Chowdhury, Facundo Mémoli |
| 2018 | Planar Graphs as L-intersection or L-contact graphs. Daniel Gonçalves, Lucas Isenmann, Claire Pennarun |
| 2018 | Polycubes with Small Perimeter Defect. Andrei Asinowski, Gill Barequet, Yufei Zheng |
| 2018 | Probabilistic Existence of Large Sets of Designs. Shachar Lovett, Sankeerth Rao, Alexander Vardy |
| 2018 | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018 Artur Czumaj |
| 2018 | Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy. Joshua Brakensiek, Venkatesan Guruswami |
| 2018 | Prophet Secretary for Combinatorial Auctions and Matroids. Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, Sahil Singla |
| 2018 | Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma. Friedrich Eisenbrand, Robert Weismantel |
| 2018 | Quasi-regular sequences and optimal schedules for security games. David Kempe, Leonard J. Schulman, Omer Tamuz |
| 2018 | Race Detection and Reachability in Nearly Series-Parallel DAGs. Kunal Agrawal, Joseph Devietti, Jeremy T. Fineman, I-Ting Angelina Lee, Robert Utterback, Changming Xu |
| 2018 | Ramsey Spanning Trees and their Applications. Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman |
| 2018 | Randomized Algorithms for Online Vector Load Balancing. Yossi Azar, Ilan Reuven Cohen, Debmalya Panigrahi |
| 2018 | Randomized MWU for Positive LPs. Chandra Chekuri, Kent Quanrud |
| 2018 | Randomized Online Matching in Regular Graphs. Ilan Reuven Cohen, David Wajc |
| 2018 | Reachability Preservers: New Extremal Bounds and Approximation Algorithms. Amir Abboud, Greg Bodwin |
| 2018 | Recognizing Weak Embeddings of Graphs. Hugo A. Akitaya, Radoslav Fulek, Csaba D. Tóth |
| 2018 | Resource-Efficient Common Randomness and Secret-Key Schemes. Badih Ghazi, T. S. Jayram |
| 2018 | Revenue Maximization with an Uncertainty-Averse Buyer. Shuchi Chawla, Kira Goldner, J. Benjamin Miller, Emmanouil Pountourakis |
| 2018 | Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart |
| 2018 | Sampling Random Colorings of Sparse Random Graphs. Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda |
| 2018 | Scheduling When You Don't Know the Number of Machines. Clifford Stein, Mingxian Zhong |
| 2018 | Separation in Correlation-Robust Monopolist Problem with Budget. Nick Gravin, Pinyan Lu |
| 2018 | Set Cover in Sub-linear Time. Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee |
| 2018 | Space-Optimal Majority in Population Protocols. Dan Alistarh, James Aspnes, Rati Gelashvili |
| 2018 | Spatial Mixing and Non-local Markov chains. Antonio Blanca, Pietro Caputo, Alistair Sinclair, Eric Vigoda |
| 2018 | Stability of the Lanczos Method for Matrix Function Approximation. Cameron Musco, Christopher Musco, Aaron Sidford |
| 2018 | Steiner Point Removal - Distant Terminals Don't (Really) Bother. Yun Kuen Cheung |
| 2018 | Steiner Point Removal with Distortion Arnold Filtser |
| 2018 | Stochastic Load Balancing on Unrelated Machines. Anupam Gupta, Amit Kumar, Viswanath Nagarajan, Xiangkun Shen |
| 2018 | Stochastic Packing Integer Programs with Few Queries. Yutaro Yamaguchi, Takanori Maehara |
| 2018 | Strong Algorithms for the Ordinal Matroid Secretary Problem. José A. Soto, Abner Turkieltaub, Victor Verdugo |
| 2018 | Submodular Minimization Under Congruency Constraints. Martin Nägele, Benny Sudakov, Rico Zenklusen |
| 2018 | Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi |
| 2018 | Syndrome decoding of Reed-Muller codes and tensor decomposition over finite fields. Swastik Kopparty, Aditya Potukuchi |
| 2018 | Targeting and Signaling in Ad Auctions. Ashwinkumar Badanidiyuru, Kshipra Bhawalkar, Haifeng Xu |
| 2018 | Testing Ising Models. Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath |
| 2018 | Testing bounded arboricity. Talya Eden, Reut Levi, Dana Ron |
| 2018 | The Bane of Low-Dimensionality Clustering. Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, Alan Roytman |
| 2018 | The Classical Complexity of Boson Sampling. Peter Clifford, Raphaël Clifford |
| 2018 | The Complexity of Counting Surjective Homomorphisms and Compactions. Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný |
| 2018 | The Complexity of Distributed Edge Coloring with Small Palettes. Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto |
| 2018 | The Diameter of Dense Random Regular Graphs. Nobutaka Shimizu |
| 2018 | The Entropy of Backwards Analysis. Mathias Bæk Tejs Knudsen, Mikkel Thorup |
| 2018 | The Gotsman-Linial Conjecture is False. Brynmor Chapman |
| 2018 | The Price of Information in Combinatorial Optimization. Sahil Singla |
| 2018 | The Robust Sensitivity of Boolean Functions. Shachar Lovett, Avishay Tal, Jiapeng Zhang |
| 2018 | The Value of Information Concealment. Hu Fu, Christopher Liaw, Pinyan Lu, Zhihao Gavin Tang |
| 2018 | The complexity of independent set reconfiguration on bipartite graphs. Daniel Lokshtanov, Amer E. Mouawad |
| 2018 | The menu complexity of "one-and-a-half-dimensional" mechanism design. Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg |
| 2018 | Thin graph classes and polynomial-time approximation schemes. Zdenek Dvorák |
| 2018 | Tight Analysis of Parallel Randomized Greedy MIS. Manuela Fischer, Andreas Noever |
| 2018 | Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs. Petra Berenbrink, George Giakkoupis, Peter Kling |
| 2018 | Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem. Sepehr Assadi, Sanjeev Khanna |
| 2018 | Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams |
| 2018 | Tightening Curves on Surfaces via Local Moves. Hsien-Chih Chang, Jeff Erickson, David Letscher, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick, Dylan Thurston, Stephan Tillmann |
| 2018 | Time and Space Efficient Representations of Distributive Lattices. J. Ian Munro, Corwin Sinnamon |
| 2018 | Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron |
| 2018 | Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2018 | Truthful Multi-Parameter Auctions with Online Supply: an Impossible Combination. Nikhil R. Devanur, Balasubramanian Sivan, Vasilis Syrgkanis |
| 2018 | Uniform generation of random graphs with power-law degree sequences. Pu Gao, Nicholas C. Wormald |
| 2018 | Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes. Aaron Sidford, Mengdi Wang, Xian Wu, Yinyu Ye |
| 2018 | Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, Oren Weimann |
| 2018 | Voronoi tessellations in the CRT and continuum random maps of finite excess. Louigi Addario-Berry, Omer Angel, Guillaume Chapuy, Éric Fusy, Christina Goldschmidt |
| 2018 | When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices. Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh |
| 2018 | Which Distribution Distances are Sublinearly Testable? Constantinos Daskalakis, Gautam Kamath, John Wright |