- Thiago Bergamaschi, Monika Henzinger
, Maximilian Probst Gutenberg
, Virginia Vassilevska Williams, Nicole Wein:
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners. SODA 2021: 1836-1855 - Sayan Bhattacharya, Fabrizio Grandoni
, David Wajc:
Online Edge Coloring Algorithms via the Nibble Method. SODA 2021: 2830-2842 - Sayan Bhattacharya, Monika Henzinger
, Danupon Nanongkai, Xiaowei Wu:
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time. SODA 2021: 2537-2549 - Andreas Björklund, Petteri Kaski:
The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid. SODA 2021: 2333-2345 - Guy Blanc, Jane Lange, Li-Yang Tan:
Query strategies for priced information, revisited. SODA 2021: 1638-1650 - Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov
, Anurag Pandey, Frank-Olaf Schreyer:
On the Orbit Closure Containment Problem and Slice Rank of Tensors. SODA 2021: 2565-2584 - Thomas Bläsius, Tobias Friedrich, Andreas Göbel, Jordi Levy
, Ralf Rothenberger
:
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability. SODA 2021: 42-53 - Greg Bodwin, Michael Dinitz
, Caleb Robelle:
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time. SODA 2021: 2924-2938 - Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-width II: small classes. SODA 2021: 1977-1996 - Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick:
On the Mysteries of MAX NAE-SAT. SODA 2021: 484-503 - Vladimir Braverman, Shaofeng H.-C. Jiang
, Robert Krauthgamer, Xuan Wu:
Coresets for Clustering in Excluded-minor Graphs and Beyond. SODA 2021: 2679-2696 - Karl Bringmann, Vasileios Nakos:
A Fine-Grained Perspective on Approximating Subset Sum and Partition. SODA 2021: 1797-1815 - Karl Bringmann, Philip Wellnitz:
On Near-Linear-Time Algorithms for Dense Subset Sum. SODA 2021: 1777-1796 - Sébastien Bubeck, Yuval Rabani, Mark Sellke:
Online Multiserver Convex Chasing and Optimization. SODA 2021: 2093-2104 - Maike Buchin, Anne Driemel
, Dennis Rohde
:
Approximating (k, ℓ-Median Clustering for Polygonal Curves. SODA 2021: 2697-2717 - Pjotr Buys, Andreas Galanis, Viresh Patel, Guus Regts:
Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs. SODA 2021: 1508-1519 - Jin-Yi Cai, Zhiguo Fu, Shuai Shao
:
New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification. SODA 2021: 1535-1547 - Yang Cai
, Kira Goldner, Steven Ma, Mingfei Zhao:
On Multi-Dimensional Gains from Trade Maximization. SODA 2021: 1079-1098 - Jin-Yi Cai, Tianyu Liu:
An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures. SODA 2021: 1520-1534 - Yang Cai
, Argyris Oikonomou, Grigoris Velegkas, Mingfei Zhao:
An Efficient ∊-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization. SODA 2021: 1337-1356 - Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi
, Erik Waingarten:
Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning. SODA 2021: 321-336 - Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, Dean Leitersdorf:
Tight Distributed Listing of Cliques. SODA 2021: 2878-2891 - Diptarka Chakraborty, Debarati Das, Robert Krauthgamer:
Approximating the Median under the Ulam Metric. SODA 2021: 761-775 - Parinya Chalermsook, Syamantak Das, Yunbum Kook, Bundit Laekhanukit, Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz:
Vertex Sparsification for Edge Connectivity. SODA 2021: 1206-1225 - Parinya Chalermsook, Bartosz Walczak:
Coloring and Maximum Weight Independent Set of Rectangles. SODA 2021: 860-868 - Erin Wolf Chambers, Jeff Erickson, Patrick Lin, Salman Parsa:
How to Morph Graphs on the Torus. SODA 2021: 2759-2778 - Timothy M. Chan:
(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems. SODA 2021: 1465-1482 - Timothy M. Chan:
Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices. SODA 2021: 1483-1495 - Karthekeyan Chandrasekaran, Chandra Chekuri:
Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions. SODA 2021: 1026-1038 - Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta:
Competitive Allocation of a Mixed Manna. SODA 2021: 1405-1424