List of accepted papers for SODA 2021

(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems

Timothy M. Chan

2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees

Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani

A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane

Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh, Subhash Suri

A Deterministic Parallel APSP Algorithm and its Applications

Adam Karczmarz, Piotr Sankowski

A Fast Minimum Degree Algorithm and Matching Lower Bound 📝

Robert Cummings, Matthew Fahrbach, Animesh Fatehpuria

A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics 📝

Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, Karol Wegrzycki

A Fine-Grained Perspective on Approximating Subset Sum and Partition

Karl Bringmann, Vasileios Nakos

A Local Search Framework for Experimental Design

Lap Chi Lau, Hong Zhou

A Lower Bound for Dynamic Fractional Cascading

Peyman Afshani

A Refined Laser Method and Faster Matrix Multiplication 📝

Josh Alman, Virginia Vassilevska Williams

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Delegation 📝

Marcel Dall'Agnol, Tom Gur, Oded Lachish

A tight condition for triangle factors in pseudorandom graphs

Patrick Morris

A Time-Optimal Randomized Parallel Algorithm for MIS

Mohsen Ghaffari, Bernhard Haeupler

A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting 📝

Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, Manolis Zampetakis

Algorithms for Persuasion with Limited Communication 📝

Ronen Gradwohl, Niklas Hahn, Martin Hoefer, Rann Smorodinsky

Algorithms for weighted independent transversals and strong colouring 📝

Alessandra Graf, David Harris, Penny Haxell

All-Pairs LCA in DAGs: Breaking through the \(O(n^{2.5})\) barrier 📝

Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Łukasiewicz, Nikos Parotsidis, Przemysław Uznański

An \(\tilde{O}(n^{5/4})\) Time \(\varepsilon\)-Approximation Algorithm for RMS Matching in a Plane 📝

Nathaniel Lahn, Sharath Raghvendra

An Efficient Epsilon-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization

Yang Cai, Argyris Oikonomou, Grigoris Velegkas, Mingfei Zhao

An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures

Jin-Yi Cai, Tianyu Liu

An improved procedure for colouring graphs of bounded local density 📝

Eoin Hurley, Rémi de Joannis de Verclos, Ross J. Kang

Analytic quantum weak coin flipping protocols with arbitrarily small bias

Atul Singh Arora, Jérémie Roland, Chrysoula Vlachou

Approximate Distance Oracles Subject to Multiple Vertex Failures 📝

Ran Duan, Yong Gu, Hanlin Ren

Approximate Evaluation of First-Order Counting Queries

Jan Dreier, Peter Rossmanith

Approximate Nearest Neighbors Beyond Space Partitions

Alexandr Andoni, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten

Approximating \((k,\ell)\)-Median Clustering for Polygonal Curves 📝

Maike Buchin, Anne Driemel, Dennis Rohde

Approximating pathwidth for graphs of small treewidth 📝

Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak

Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler 📝

Zhihan Jin, Zhengfeng Ji, Pinyan Lu

Approximating the Median under the Ulam Metric

Diptarka Chakraborty, Debarati Das, Robert Krauthgamer

Approximation Algorithms and Hardness for Strong Unique Games 📝

Suprovat Ghoshal, Anand Louis

Asymptotic dimension of minor-closed families and beyond 📝

Chun-Hung Liu

Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model

Michael Goodrich, Riko Jacob, Nodari Sitchinava

Average Sensitivity of Graph Algorithms 📝

Nithin Varma, Yuichi Yoshida

Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions 📝

Mahsa Derakhshan, David Pennock, Aleksandrs Slivkins

Beating the probabilistic lower bound on perfect hashing 📝

Chaoping Xing, Chen Yuan

Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners 📝

Peter Robinson

Beyond Submodular Maximization via One-Sided Smoothness 📝

Mehrdad Ghadiri, Richard Santiago, Bruce Shepherd

Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time 📝

Jana Cslovjecsek, Friedrich Eisenbrand, Christoph Hunkenschröder, Lars Rohwedder, Robert Weismantel

Branch-and-Bound Solves Random Binary Packing IPs in Polytime 📝

Yatharth Dubey, Santanu Dey, Marco Molinaro

Can We Beat the AKS Sorting Network?

Gilad Asharov, Wei-Kai Lin, Elaine Shi

Coloring and Maximum Weight Independent Set of Rectangles 📝

Parinya Chalermsook, Bartosz Walczak

Competitive Allocation of a Mixed Manna 📝

Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta

Competitive Data-Structure Dynamization

Claire Mathieu, Rajmohan Rajaraman, Neal Young, Arman Yousefi

Concentration bounds for almost k-wise independence with applications to non-uniform security

Nick Gravin, Siyao Guo, Tsz Chiu Kwok, Pinyan Lu

Connecting Robust Shuffle Privacy and Pan-Privacy 📝

Victor Balcer, Albert Cheu, Matthew Joseph, Jieming Mao

Consistent k-Clustering for General Metrics

Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson

Constrained-Order Prophet Inequalities

Makis Arsenis, Odysseas Drosis, Robert Kleinberg

Coresets for Clustering in Excluded-minor Graphs and Beyond 📝

Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu

Counting Homomorphisms to \(K_4\)-minor-free Graphs, modulo 2 📝

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Živný

Counting Small Permutation Patterns

Chaim Even-Zohar, Calvin Leng

Decomposing the Complement of the Union of Cubes in Three Dimensions

Pankaj K. Agarwal, Micha Sharir, Alex Steiger

Deep Weisfeiler Leman 📝

Martin Grohe, Pascal Schweitzer, Daniel Wiebking

Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition 📝

Julia Chuzhoy, Thatchaphol Saranurak

Deterministic Replacement Path Covering 📝

Karthik C. S., Merav Parter

Dimension-Preserving Reductions Between SVP and CVP in Different \(p\)-Norms

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz

Directed Shortest Paths via Approximate Cost Balancing 📝

James B. Orlin, László Végh

Distributed Metropolis Sampler with Optimal Parallelism 📝

Weiming Feng, Thomas P. Hayes, Yitong Yin

Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model 📝

Krzysztof Nowicki, Krzysztof Onak

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications 📝

Sebastian Forster, Gramoz Goranci, Monika Henzinger

Dynamic Set Cover: Improved Amortized and Worst-Case Update Times 📝

Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu

Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting

Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi

Efficient Document Exchange and Error Correcting Codes with Asymmetric Information 📝

Kuan Cheng, Xin Li

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles 📝

Jiehua Chen, Wojciech Czerwiński, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Michał Pilipczuk, Marcin Pilipczuk, Manuel Sorge, Bartłomiej Wróblewski, Anna Zych-Pawlewicz

Efficient Linear and Affine Codes for Correcting Insertions/Deletions 📝

Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li

EPTAS for \(k\)-means Clustering of Affine Subspaces

Eduard Eiben, Fedor Fomin, Petr A. Golovach, Willian Lochet, Fahad Panolan, Kirill Simonov

Estimating the Nash Social Welfare for coverage and other submodular valuations

Jan Vondrak, Wenzheng Li

Explicit two-deletion codes with redundancy matching the existential bound 📝

Venkatesan Guruswami, Johan Håstad

Fast Convergence of Fictitious Play for Diagonal Payoff Matrices 📝

Jacob Abernethy, Kevin A. Lai, Andre Wibisono

Fast Low-Space Algorithms for Subset Sum

Ce Jin, Nikhil Vyas, Ryan Williams

Fine-grained hardness of CVP(P) — Everything that we can prove (and nothing else) 📝

Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz

FPT Approximation for FPT Problems

Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi

Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model 📝

Arnold Filtser, Michael Kapralov, Navid Nouri

Hamiltonicity of random subgraphs of the hypercube 📝

Alberto Espuny Díaz, Padraig Condon, António Girão, Daniela Kühn, Deryk Osthus

Hardness of Approximation for Orienteering with Multiple Time Windows

Naveen Garg, Sanjeev Khanna, Amit Kumar

How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices? 📝

Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga

How to Morph Graphs on the Torus 📝

Erin Wolf Chambers, Jeff Erickson, Patrick Lin, Salman Parsa

Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting 📝

Itai Dinur

Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover 📝

Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali

Improved Deterministic Network Decomposition 📝

Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň

Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier 📝

Sepehr Assadi, Thomas Kesselheim, Sahil Singla

Improving the dilation of a metric graph by adding edges 📝

Joachim Gudmundsson, Sampson Wong

Incremental Single Source Shortest Paths in Sparse Digraphs

Shiri Chechik, Tianyi Zhang

Induced subgraphs of bounded treewidth and the container method 📝

Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, Paul Seymour

Infinite-Duration All-Pay Bidding Games 📝

Guy Avni, Ismael Jecker, Djordje Zikelic

Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs 📝

Pjotr Buys, Andreas Galanis, Viresh Patel, Guus Regts

List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time

Ainesh Bakshi, Pravesh K. Kothari

Local Statistics, Semidefinite Programming, and Community Detection 📝

Jess Banks, Sidhanth Mohanty, Prasad Raghavendra

Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions

Karthekeyan Chandrasekaran, Chandra Chekuri

Minimizing Convex Functions with Integral Minimizers 📝

Haotian Jiang

Minimum-cost integer circulations in given homology classes 📝

Sarah Morell, Ina Seidel, Stefan Weltge

Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles

Suman Kalyan Bera, Noujan Pashanasangi, C. Seshadhri

Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices

Timothy M. Chan

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

Shuichi Hirahara, Nobutaka Shimizu

New Data Structures for Orthogonal Range Reporting and Range Minima Queries 📝

Yakov Nekrich

New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification

Jin-Yi Cai, Zhiguo Fu, Shuai Shao

New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners

Thiago Bergamaschi, Monika Henzinger, Maximilian Probst, Virginia Vassilevska Williams, Nicole Wein

Non-linear Hamilton cycles in linear quasi-random hypergraphs

Jie Han, Xichao Shu, Guanghui Wang

Non-Separable Dynamic Mechanism Design

Santiago Balseiro, Vahab Mirrokni, Renato Paes Leme, Song Zuo

Non-uniform Geometric Set Cover and Scheduling on Multiple Machines 📝

Jatin Batra, Nikhil Bansal

On a combinatorial generation problem of Knuth 📝

Arturo Merino, Ondřej Mička, Torsten Mütze

On Approximability of Clustering Problems Without Candidate Centers 📝

Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

On Efficient Distance Approximation for Graph Properties 📝

Nimrod Fiat, Dana Ron

On Indexing and Compressing Finite Automata 📝

Nicola Cotumaccio, Nicola Prezza

On Locating Paths in Compressed Tries 📝

Nicola Prezza

On Multi-Dimensional Gains from Trade Maximization 📝

Yang Cai, Kira Goldner, Steven Ma, Mingfei Zhao

On Near-Linear-Time Algorithms for Dense Subset Sum

Karl Bringmann, Philip Wellnitz

On Testability of First-Order Properties in Bounded-Degree Graphs 📝

Isolde Adler, Noleen Köhler, Pan Peng

On the Competitive Analysis and High Accuracy Optimality of Profile Maximum Likelihood 📝

Yanjun Han, Kirankumar Shiragur

On the Mysteries of MAX NAE-SAT 📝

Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick

On the Orbit Closure Containment Problem and Slice Rank of Tensors

Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, Frank-Olaf Schreyer

On Two-Handed Planar Assembly Partitioning 📝

Pankaj Agarwal, Boris Aronov, Tzvika Geft, Dan Halperin

Online Combinatorial Auctions

Yuan Deng, Debmalya Panigrahi, Hanrui Zhang

Online Discrepancy Minimization for Stochastic Arrivals 📝

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

Online Edge Coloring Algorithms via the Nibble Method

Sayan Bhattacharya, Fabrizio Grandoni, David Wajc

Online Generalized Network Design Under (Dis)Economies of Scale 📝

Viswanath Nagarajan, Lily Wang

Online Multiserver Convex Chasing and Optimization 📝

Mark Sellke, Sebastien Bubeck, Yuval Rabani

Optimal \(\ell_1\) Column Subset Selection and a Fast PTAS for Low Rank Approximation 📝

Arvind Mahankali, David P. Woodruff

Optimal Contextual Pricing and Extensions 📝

Allen Liu, Renato Paes Leme, Jon Schneider

Optimal Discretization is Fixed-parameter Tractable 📝

Stefan Kratsch, Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge

Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness

Dana Ron, Asaf Rosin

Optimal Girth Approximation for Dense Directed Graphs

Shiri Chechik, Gur Lifshitz

Optimal Inapproximability with Universal Factor Graphs 📝

Per Austrin, Jonah Brown-Cohen, Johan Håstad

Optimal Oblivious Priority Queues 📝

Zahra Jafargholi, Kasper Green Larsen, Mark Simkin

Optimal Vertex Fault-Tolerant Spanners in Polynomial Time 📝

Greg Bodwin, Michael Dinitz, Caleb Robelle

Peeling Close to the Orientability Threshold: Spatial Coupling in Hashing-Based Data Structures 📝

Stefan Walzer

Planar Distance Oracles with Better Time-Space Tradeoffs 📝

Yaowei Long, Seth Pettie

Planar Negative k-Cycle

Pawel Gawrychowski, Shay Mozes, Oren Weimann

Planar Reachability Under Single Vertex or Edge Failures

Giuseppe F. Italiano, Adam Karczmarz, Nikos Parotsidis

Polyhedral value iteration for discounted games and energy games 📝

Alexander Kozachinskiy

Polynomial-time trace reconstruction in the smoothed complexity model 📝

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha

Population Recovery from the Deletion Channel: Nearly Matching Trace Reconstruction Bounds 📝

Shyam Narayanan

PTAS for Minimum Cost Multi-covering with Disks

Ziyun Huang, Qilong Feng, Jianxin Wang, Jinhui Xu

Quantum algorithms for graph problems with cut queries 📝

Troy Lee, Miklos Santha, Shengyu Zhang

Query strategies for priced information revisited

Guy Blanc, Jane Lange, Li-Yang Tan

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning 📝

Clément Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten

Randomized Cup Game Algorithms Against Strong Adversaries

Michael A. Bender, William Kuszmaul

Rankwidth meets stability 📝

Jaroslav Nesetril, Patrice Ossona de Mendez, Michał Pilipczuk, Roman Rabinovich, Sebastian Siebertz

Rapid Mixing for Colorings via Spectral Independence 📝

Zongchen Chen, Andreas Galanis, Daniel Štefankovič, Eric Vigoda

Rapid mixing from spectral independence beyond the Boolean domain 📝

Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang

Robust Algorithms for Online Convex Problems

Marco Molinaro

Robust Learning of Mixtures of Gaussians 📝

Daniel M. Kane

Rolling backwards can move you forward: on embedding problems in sparse expanders 📝

Nemanja Draganic, Michael Krivelevich, Rajko Nenadov

Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines

Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang

Self-Stabilizing Clock Synchronization with 1-bit Messages

Paul Bastide, George Giakkoupis, Hayk Saribekyan

Shorter Labels for Routing in Trees 📝

Paweł Gawrychowski, Wojciech Janczewski, Jakub Łopuszański

Shortest Paths Among Obstacles in the Plane Revisited

Haitao Wang

Solving hard cut problems via flow-augmentation 📝

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlstrom

Solving Sparse Linear Systems Faster than Matrix Multiplication 📝

Richard Peng, Santosh Vempala

SOS degree reduction with applications to clustering and robust moment estimation

David Steurer, Stefan Tiegel

Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model

Michael Kapralov

Spectral Clustering Oracles in Sublinear Time

Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, Christian Sohler

Spectral Sparsification of Metrics and Kernels

Kent Quanrud

Static and Streaming Data Structures for Fréchet Distance Queries 📝

Arnold Filtser, Omrit Filtser

Streaming Submodular Matching Meets the Primal-Dual Method 📝

Roie Levin, David Wajc

Strong Connectivity Augmentation is FPT

Pranabendu Misra, Kristine Vitting Klinkby, Saket Saurabh

Strongly refuting all semi-random Boolean CSPs 📝

Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari

Sublinear Time Algorithms for Longest Increasing Subsequence

Michael Mitzenmacher, Saeed Seddighin

The Connectivity Threshold for Dense Graphs

Anupam Gupta, Euiwoong Lee, Jason Li

The Demand Query Model for Bipartite Matching 📝

Noam Nisan

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms 📝

Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, Zihan Tan

The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid 📝

Andreas Björklund, Petteri Kaski

The growth rate over trees of any family of sets defined by a monadic second order formula is semi-computable 📝

Matthieu Rosenfeld

The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability 📝

Thomas Bläsius, Tobias Friedrich, Andreas Göbel, Jordi Levy, Ralf Rothenberger

The Min-Cost Matching with Concave Delays Problem

Yossi Azar, Runtian Ren, Danny Vainstein

The Secretary Problem with Independent Sampling

José Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, Alexandros Tsigonias-Dimitriadis

The shortest disjoint paths problem 📝

William Lochet

Tight Bounds for Online Graph Partitioning

Monika Henzinger, Stefan Neumann, Harald Räcke, Stefan Schmid

Tight Bounds for Parallel Paging and Green Paging

Kunal Agrawal, Michael Bender, Rathish Das, William Kuszmaul, Enoch Peserico, Michele Scquizzato

Tight Distributed Listing of Cliques

Keren Censor-Hillel, Yi-Jun Chang, Francois Le Gall, Dean Leitersdorf

Tight Distributed Sketching Lower Bound for Connectivity 📝

Huacheng Yu

Tolerant Distribution Testing in the Conditional Sampling Model 📝

Shyam Narayanan

Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms 📝

Shi Li

Treewidth-Pliability and PTAS for Max-CSPs 📝

Miguel Romero, Marcin Wrochna, Stanislav Živný

Twin-width II: small classes 📝

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

Two-stage Stochastic Matching with Application to Ride Hailing

Yiding Feng, Rad Niazadeh, Amin Saberi

Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

Arun Jambulapati, Aaron Sidford

Uncertainty about Uncertainty: Near-Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins 📝

Jasper C.H. Lee, Paul Valiant

Unlinking, splitting, and some other NP-hard problems in knot theory 📝

Dale Koenig, Anastasiia Tsvietkova

Vertex Sparsification for Edge Connectivity 📝

Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Yunbum Kook, Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz

Which Random Matching Markets Exhibit a Stark Effect of Competition? 📝

Yash Kanoria, Seungki Min, Pengyu Qian