SODA21 Accepted Papers | SIAM

Accepted Papers

Visualizer: Accepted Papers

Paper titles and author information appears as submitted.

Paper title and author changes will not be made to this page. The online program will reflect the most up-to-date presentation details, and is scheduled for posting in November.

(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 Zivny

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, Marcin Pilipczuk, Michał 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, Vaclav Rozhon

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 and 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
Clement 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 Stefankovic, 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
Pawel Gawrychowski, Wojciech Janczewski, Jakub Lopuszanski

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
Jose Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, Alexandros Tsigonias-Dimitriadis

The shortest disjoint paths problem
Lochet William

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 Zivny

Twin-width II: small classes
Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Tomassé, 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