Papers accepted to SODA 2018:

· Ken-Ichi Kawarabayashi and Benjamin Rossman. A Polynomial Excluded-Minor Approximation of Treedepth.

· David Kempe, Leonard J. Schulman and Omer Tamuz. Quasi-regular sequences and optimal schedules for security games.

· Constantinos Daskalakis, Gautam Kamath and John Wright. Which Distribution Distances are Sublinearly Testable?

· Constantinos Daskalakis, Nishanth Dikkala and Gautam Kamath. Testing Ising Models.

· Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra and Alistair Stewart. Robustly Learning a Gaussian: Getting Optimal Error, Efficiently.

· Ilan R. Cohen and David Wajc. Randomized Online Matching in Regular Graphs.

· Chenglin Fan, Benjamin Raichel and Gregory Van Buskirk. Metric Violation Distance: Hardness and Approximation.

· Hugo Akitaya, Radoslav Fulek and Csaba Toth. Recognizing Weak Embeddings of Graphs.

· David Harris. Derandomized concentration bounds for polynomials, and hypergraph maximal independent set.

· Siqi Liu and Christos-Alexandros Psomas. On the Competition Complexity of Dynamic Mechanism Design.

· Aaron Bernstein, Jacob Holm and Eva Rotenberg. Online bipartite matching with amortized O(log² n) replacements.

· Mathias Bæk Tejs Knudsen and Mikkel Thorup. The Entropy of Backwards Analysis.

· Nicola Prezza. In-Place Sparse Suffix Sorting.

· Timothy M. Chan. More Logarithmic-Factor Speedups for 3SUM, (median,+)-Convolution, and Some Geometric 3SUM-Hard Problems.

· Keerti Choudhary, Surender Baswana, Moazzam Hussain and Liam Roditty. Approximate Single Source Fault Tolerant Shortest Path.

· Mitchell Jones and Sariel Har-Peled. On Separating Points by Lines.

· Ramanujan M. S., Daniel Lokshtanov and Saket Saurabh. When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices.

· Karl Bringmann, Pawel Gawrychowski, Shay Mozes and Oren Weimann. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).

· Lin Chen and Dániel Marx. Covering a tree with rooted subtrees -- parameterized and approximation algorithms.

· Zdenek Dvorak. Thin graph classes and polynomial-time approximation schemes.

· Jacob Holm, Eva Rotenberg and Mikkel Thorup. Dynamic Bridge-Finding in Õ(log² n) Amortized Time.

· Chloe Ching-Yun Hsu and Chris Umans. A fast generalized DFT for finite groups of Lie type.

· Hadley Black, Deeparnab Chakrabarty and C. Seshadhri. A o(d)polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]^d.

· Arnold Filtser. Steiner Point Removal with Distortion O(log k).

· Shay Mozes, Cyril Nikolaev, Yahav Nussbaum and Oren Weimann. Minimum Cut of Directed Planar Graphs in O(nloglogn) Time.

· Chaya Keller and Shakhar Smorodinsky. Conflict-Free Coloring of Intersection Graphs of Geometric Objects.

· Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn and Claire Mathieu. Hierarchical Clustering: Objective Functions and Algorithms.

· Moran Feldman, Ola Svensson and Rico Zenklusen. A Framework for the Secretary Problem on the Intersection of Matroids.

· Guillaume Lagarde and Sylvain Perifel. Lempel-Ziv: a "one-bit catastrophe" but not a tragedy.

· Samir Chowdhury and Facundo Memoli. Persistent Path Homology of Directed Networks.

· Takanori Maehara and Yutaro Yamaguchi. Stochastic Packing Integer Program with Few Queries.

· Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan and Pan Xu. Algorithms to Approximate Column-Sparse Packing Problems.

· Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger and Veronika Loitzenbauer. Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter.

· Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick and Martin Tancer. Embeddability in R³ is NP-hard.

· Jacob Focke, Leslie Ann Goldberg and Stanislav Živný. The Complexity of Counting Surjective Homomorphisms and Compactions.

· S. Matthew Weinberg, Raghuvansh R. Saxena and Ariel Schvartzman. The menu complexity of one-and-a-half-dimensional mechanism design.

· Andrei Asinowski, Gill Barequet and Yufei Zheng. Polycubes with Small Perimeter Defect.

· Surender Baswana, Ayush Goel and Shahbaz Khan. Incremental DFS algorithms: a theoretical and experimental study.

· Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma.

· Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva and Devanathan Thiruvenkatachari. Near-optimal approximation algorithm for simultaneous Max-Cut.

· Amir Abboud, Pawel Gawrychowski, Shay Mozes and Oren Weimann. Near-Optimal Compression for the Planar Graph Metric.

· Anne Driemel and Peyman Afshani. On the complexity of range searching among curves.

· Vincent Cohen-Addad. A Fast Approximation Scheme for Low-Dimensional k-Means.

· Soheil Ehsani, Mohammadtaghi Hajiaghayi, Thomas Kesselheim and Sahil Singla. Prophet Secretary for Combinatorial Auctions and Matroids.

· Sahil Singla. The Price of Information in Combinatorial Optimization.

· Krzysztof Nowicki and Tomasz Jurdzinski. MST in O(1) Rounds of Congested Clique.

· Mark Braverman, Jieming Mao and S. Matthew Weinberg. On Simultaneous Two-player Combinatorial Auctions.

· Nikola Yolov. Minor-matching hypertree width.

· Joe Sawada and Aaron Williams. A Hamilton Path for the Sigma-Tau Problem.

· Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma and Meirav Zehavi. Covering small independent sets and separators with applications to parameterized algorithms.

· Abishek Sankararaman and François Baccelli. Community Detection on Euclidean Random Graphs.

· Peter Clifford and Raphael Clifford. The Classical Complexity of Boson Sampling.

· Samuel Fiorini, Martin Groß, Jochen Koenemann and Laura Sanita. Approximating Weighted Tree Augmentation via Chvatal-Gomory Cuts.

· Joshua Brakensiek and Venkatesan Guruswami. Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy.

· Ross Churchley and Bojan Mohar. A submodular measure and approximate Gomory-Hu theorem for packing odd trails.

· Don Sheehy. Frechet-Stable Signatures Using Persistence Homology.

· Pu Gao and Nicholas Wormald. Uniform generation of random graphs with power-law degree sequences.

· Swastik Kopparty and Aditya Potukuchi. Syndrome decoding of Reed-Muller codes and tensor decompositions over finite fields.

· Clifford Stein and Mingxian Zhong. Scheduling When You Don't Know the Number of Machines.

· Leszek Gasieniec and Grzegorz Stachowiak. Fast Space Optimal Leader Election in Population Protocols.

· Sankeerth Rao Karingula, Shachar Lovett and Alexander Vardy. Probabilistic Existence of Large Sets of Designs.

· Jugal Garg, Martin Hoefer and Kurt Mehlhorn. Approximating the Nash Social Welfare with Budget-Additive Valuations.

· Anupam Gupta, Euiwoong Lee and Jason Li. An FPT Algorithm Beating 2-Approximation for k-Cut.

· Eldar Fischer, Frederic Magniez and Tatiana Starikovskaya. Improved bounds for testing Dyck languages.

· Stephen Alstrup, Agelos Georgakopoulos, Eva Rotenberg and Carsten Thomassen. A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time.

· Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser and Ofer Neiman. Ramsey Spanning Trees and their Applications.

· Shachar Lovett, Avishay Tal and Jiapeng Zhang. The Robust Sensitivity of Boolean Functions.

· Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir and Oren Weimann. Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n^5/3) time.

· Huan Li and Zhongzhi Zhang. Kirchhoff Index as a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms.

· Xi Chen, Yuanzhi Li and Jieming Mao. An Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model.

· Anindya De. Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack.

· Peter Franek, Marek Filakovský, Stephan Zhechev and Uli Wagner. Computing Simplicial Representatives of Homotopy Group Elements.

· Anindya De, Elchanan Mossel and Joe Neeman. Non interactive simulation of correlated distributions is decidable.

· Eric Blais, Clément Canonne, Talya Eden, Amit Levi and Dana Ron. Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.

· Vincent Cohen-Addad, Éric Colin de Verdière and Arnaud de Mesmay. A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals.

· Yossi Azar, Ilan Cohen and Debmalya Panigrahi. Randomized Algorithms for Online Vector Load Balancing.

· Harry Lang. Online Facility Location against a t-Bounded Adversary.

· Vera Traub and Jens Vygen. Approaching 3/2 for the s-t-path TSP.

· Vahab Mirrokni, Mikkel Thorup and Morteza Zadimoghaddam. Consistent Hashing with Bounded Loads.

· Martin Nägele, Benny Sudakov and Rico Zenklusen. Submodular Minimization Under Congruency Constraints.

· François Le Gall and Florent Urrutia. Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor.

· Greg Bodwin, Michael Dinitz, Merav Parter and Virginia Vassilevska Williams. Optimal Vertex Fault Tolerant Spanners (for fixed stretch).

· Daniel Dadush, Cristobal Guzman and Neil Olver. Fast, Deterministic and Sparse Dimensionality Reduction.

· Amir Abboud and Greg Bodwin. Reachability Sparsifiers: New Extremal Bounds and Approximation Algorithms.

· Anupam Gupta, Amit Kumar, Viswanath Nagarajan and Xiangkun Shen. Stochastic Load Balancing on Unrelated Machines.

· Omri Ben-Eliezer and Clément Canonne. Improved bounds for testing forbidden order patterns.

· Kunal Agrawal, Joseph Devietti, Jeremy Fineman, I-Ting Angelina Lee, Robert Utterback and Changming Xu. Race Detection and Reachability in Nearly Series-Parallel DAGs.

· Venkatesan Guruswami and Ray Li. Coding against deletions in oblivious and online models.

· T-H. Hubert Chan, Yue Guo, Wei-Kai Lin and Elaine Shi. Cache-Oblivious and Data-Oblivious Sorting and Applications.

· Louigi Addario-Berry, Omer Angel, Guillaume Chapuy, Eric Fusy and Christina Goldschmidt. Voronoi tessellations in the CRT and continuum random maps of finite excess.

· Jaroslaw Blasiok. Optimal streaming and tracking distinct elements with high probability.

· Christopher De Sa, Albert Gu, Rohan Puttagunta, Christopher Re and Atri Rudra. A two-pronged progress in structured dense matrix vector multiplication.

· José A. Soto, Victor Verdugo and Abner Turkieltaub. Strong Algorithms for the Ordinal Matroid Secretary Problem.

· Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov and Virginia Vassilevska Williams. Approximating Cycles in Directed Graphs.

· Andrea Lincoln, Virginia Vassilevska Williams and Ryan Williams. Tight Hardness for Shortest Cycles and Paths in Sparse Graphs.

· Daniel Dadush, László A. Végh and Giacomo Zambelli. Geometric Rescaling Algorithms for Submodular Function Minimization.

· Satish Rao, Nikhil Srivastava and Aaron Schild. Localization of Electrical Flows.

· Wai Ming Tai and Jeff Phillips. Improved Coresets for Kernel Density Estimates.

· Hu Fu, Chris Liaw, Pinyan Lu and Zhihao Gavin Tang. The Value of Information Concealment.

· Ehsan Emamjomeh-Zadeh and David Kempe. Adaptive Hierarchical Clustering Using Ordinal Queries.

· Sharath Raghvendra and Mariëtte C. Wessels. A Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problem.

· Aaron Sidford, Mengdi Wang, Xian Wu and Yinyu Ye. Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes.

· Jin-Yi Cai, Pinyan Lu and Mingji Xia. Dichotomy for Real Holant^c Problems.

· Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn and Sharath Raghvendra. A Faster Algorithm for the Minimum-Cost Bipartite Perfect Matching in Planar Graphs.

· Benjamin Plaut and Tim Roughgarden. Almost Envy-Freeness with General Valuations.

· Gábor Ivanyos and Youming Qiao. Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing.

· David Durfee, Matthew Fahrbach, Yu Gao and Tao Xiao. Nearly Tight Bounds for Sandpile Transience on the Grid.

· Makrand Sinha. Lower Bounds for Approximating the Matching Polytope.

· Atri Rudra and Mary Wootters. Average-radius list-recoverability of random linear codes.

· Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour and Mohammad Salavatipour. Approximation Schemes for Clustering Problems with Outliers.

· Arun Jambulapati and Aaron Sidford. Efficient Õ(n/) Spectral Sketches for the Laplacian and its Pseudoinverse.

· Fang-Yi Yu and Grant Schoenebeck. Consensus of Interacting Particle Systems on Erdos-Renyi Graphs.

· Xi Chen, George Matikas, Dimitris Paparas and Mihalis Yannakakis. On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer.

· Travis Gagie, Gonzalo Navarro and Nicola Prezza. Optimal-Time Text Indexing in BWT-runs Bounded Space.

· Nima Anari, Shayan Oveis Gharan, Amin Saberi and Nikhil Srivastava. Approximating the Largest Root and Applications to Interlacing Families.

· Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian and Anak Yodpinyanee. Set Cover in Sub-linear Time.

· Karthekeyan Chandrasekaran, Chao Xu and Xilin Yu. Hypergraph k-Cut in Randomized Polynomial Time.

· Sina Dehghani, Alireza Farhadi, Mohammadtaghi Hajiaghayi and Hadi Yami. Envy-free Chore Division for An Arbitrary Number of Agents.

· Hsien-Chih Chang, Jeff Erickson, David Letscher, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick, Dylan Thurston and Stephan Tillmann. Minimizing Intersections of Curves on Surfaces via Local Moves.

· Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg and Alan Roytman. The Bane of Low-Dimensionality Clustering.

· Nikolai Gravin and Pinyan Lu. Separation in Correlation-Robust Monopolist Problem with Budget.

· Adrian Kosowski and Przemysław Uznański. Ergodic Effects in Token Circulation.

· Charilaos Efthymiou, Thomas Hayes, Daniel Stefankovic and Eric Vigoda. Sampling Random Colorings of Sparse Random Graphs.

· Paweł Gawrychowski, Shay Mozes, Oren Weimann and Christian Wulff-Nilsen. Better Tradeoffs for Exact Distance Oracle in Planar Graphs.

· Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger and Danupon Nanongkai. Dynamic Algorithms for Graph Coloring.

· Daniel Gonçalves, Lucas Isenmann and Claire Pennarun. Planar Graphs as L-intersection or L-contact graphs.

· Aaron Bernstein and Shiri Chechik. Incremental Topological Sort and Cycle Detection in Õ(m ) Expected Total Time.

· Assaf Naor, Gilles Pisier and Gideon Schechtman. Impossibility of dimension reduction in the nuclear norm.

· Erin Wolf Chambers, Arnaud de Mesmay and Tim Ophelders. On the complexity of optimal homotopies.

· Daniel Lokshtanov and Amer Mouawad. The complexity of independent set reconfiguration on bipartite graphs.

· Zhiyi Huang and Xue Zhu. Better Jointly Private Packing Algorithm via Dual Multiplicative Weight Update.

· Mateus De Oliveira Oliveira. A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth.

· Nicholas Harvey, Piyush Srivastava and Jan Vondrak. Computing the Independence Polynomial: from the Tree Threshold down to the Roots.

· Kristof Berczi, Karthekeyan Chandrasekaran, Tamas Kiraly and Vivek Madan. A tight -approximation for Linear 3-Cut.

· David Coudert, Guillaume Ducoffe and Alexandru Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs.

· Manuela Fischer and Andreas Noever. Tight Analysis of Parallel Randomized Greedy MIS.

· Soheil Ehsani, Mohammad Ghodsi, Mohammadtaghi Hajiaghayi, Mahdi Safarnejad-Boroujeni and Saeed Seddighin. Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce.

· Nobutaka Shimizu. The Diameter of Dense Random Regular Graphs.

· Panayotis Mertikopoulos, Christos Papadimitriou and Georgios Piliouras. Cycles in Adversarial Regularized Learning.

· Reza Gheissari, Eyal Lubetzky and Yuval Peres. Exponentially slow mixing in the mean-field Swendsen--Wang dynamics.

· Sepehr Assadi and Sanjeev Khanna. Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem.

· Talya Eden, Reut Levi and Dana Ron. Testing bounded arboricity.

· Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stephan Thomasse and Meirav Zehavi. Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems.

· Alfonso Cevallos, Stefan Weltge and Rico Zenklusen. Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting.

· Yun Kuen Cheung. Steiner Point Removal --- Distant Terminals Don't (Really) Bother.

· Nikhil Bansal, Martin Böhm, Marek Elias, Grigorios Koumoutsos and Seeun William Umboh. Nested Convex Bodies Are Chaseable.

· Nikhil Bansal, Marek Elias, Grigorios Koumoutsos and Jesper Nederlof. Competitive Algorithms for Generalized k-Server in Uniform Metrics.

· Pawel Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Łącki and Piotr Sankowski. Optimal Dynamic Strings.

· Eun Jung Kim and O-Joung Kwon. Erdos-Posa property of chordless cycles and its applications.

· Pooya Hatami and Madhur Tulsiani. Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius.

· Radu Curticapean, Jesper Nederlof and Nathan Lindzey. Tight lower bounds for counting Hamiltonian cycles via matrix rank.

· Pan Peng and Christian Sohler. Estimating Graph Parameters from Random Order Streams.

· Dan Alistarh, James Aspnes and Rati Gelashvili. Space-Optimal Majority in Population Protocols.

· Amir Nayyeri and Hanzhong Xu. On the Decidability of the Frechet Distance between Surfaces.

· Antonio Blanca, Pietro Caputo, Alistair Sinclair and Eric Vigoda. Spatial Mixing and Non-local Markov chains.

· Mohit Singh and Weijun Xie. Approximate Positive Correlated Distributions and Approximation Algorithms for D-optimal Design.

· Chandra Chekuri and Kent Quanrud. Randomized MWU for Positive LPs.

· Karl Bringmann and Marvin Künnemann. Multivariate Fine-Grained Complexity of Longest Common Subsequence.

· Petr Golovach, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth.

· Shuchi Chawla, Kira Goldner, J. Benjamin Miller and Emmanouil Pountourakis. Aversion to Uncertainty and Its Implications for Revenue Maximization.

· Ashwinkumar Badanidiyuru, Kshipra Bhawalkar and Haifeng Xu. Targeting and Signaling in Ad Auctions.

· Nima Anari, Tung Mai, Shayan Oveis Gharan and Vijay Vazirani. Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities.

· Nikhil Srivastava and Luca Trevisan. An Alon-Boppana type bound for weighted graphs and lower bounds for spectral sparsification.

· Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay Vazirani and Sadra Yazdanbod. A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications.

· Badih Ghazi and T.S. Jayram. Resource-Efficient Common Randomness and Secret-Key Schemes.

· Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammadtaghi Hajiaghayi, Mohammad Mahdian, Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin and Philip B. Stark. From Battlefields to Presidential Elections: Winning Strategies of Blotto and Auditing Games.

· J. Ian Munro and Corwin Sinnamon. Time and Space Efficient Representations of Distributive Lattices.

· Anna Ben-Hamou, Eyal Lubetzky and Yuval Peres. Comparing mixing times on sparse random graphs.

· Cameron Musco, Christopher Musco and Aaron Sidford. Stability of the Lanczos Method for Matrix Function Approximation.

· Brynmor Chapman. The Gotsman-Linial Conjecture is False.

· Flavio Chierichetti, Ravi Kumar and Andrew Tomkins. Discrete Choice, Permutations, and Reconstruction.

· Petra Berenbrink, George Giakkoupis and Peter Kling. Tight Bounds for Coalescing Branching Random Walks on Regular Graphs.

· Joergen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, Ramanujan M. S., Saket Saurabh and Meirav Zehavi. Parameterized Algorithms for Survivable Network Design with Uniform Demands.

· Nikhil R. Devanur, Balasubramanian Sivan and Vasilis Syrgkanis. Truthful Multi-Parameter Auctions with Online Supply: an Impossible Combination.

· Adam Karczmarz. Decremental Transitive Closure and Shortest Paths for Planar Digraphs and Beyond.

· Anna Ben-Hamou, Roberto I. Oliveira and Yuval Peres. Estimating graph parameters via random walks with restarts.

· Daniel Lokshtanov, Ivan Mihajlin, Ramamohan Paturi and Pavel Pudlák. Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth.

· Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie and Jara Uitto. The Complexity of Distributed Edge Coloring with Small Palettes.

· Ryan Williams. On the Complexity of Furthest, Closest, and Orthogonal Pairs in Low Dimensions.

· Pawel Gawrychowski, Fabian Kuhn, Jakub Lopuszanski, Konstantinos Panagiotou and Pascal Su. Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees.