- 2021
- Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari:
Strongly refuting all semi-random Boolean CSPs. SODA 2021: 454-472 - Jacob D. Abernethy, Kevin A. Lai, Andre Wibisono:
Fast Convergence of Fictitious Play for Diagonal Payoff Matrices. SODA 2021: 1387-1404 - Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk
, Pawel Rzazewski
, Paul D. Seymour:
Induced subgraphs of bounded treewidth and the container method. SODA 2021: 1948-1964 - Isolde Adler, Noleen Köhler
, Pan Peng:
On Testability of First-Order Properties in Bounded-Degree Graphs. SODA 2021: 1578-1597 - Peyman Afshani:
A Lower Bound for Dynamic Fractional Cascading. SODA 2021: 2229-2248 - Pankaj K. Agarwal, Boris Aronov, Tzvika Geft, Dan Halperin:
On Two-Handed Planar Assembly Partitioning with Connectivity Constraints. SODA 2021: 1740-1756 - Pankaj K. Agarwal, Micha Sharir, Alex Steiger:
Decomposing the Complement of the Union of Cubes in Three Dimensions. SODA 2021: 1425-1444 - Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz:
Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else). SODA 2021: 1816-1835 - Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li
, Noah Stephens-Davidowitz:
Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms. SODA 2021: 2444-2462 - Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, Michele Scquizzato:
Tight Bounds for Parallel Paging and Green Paging. SODA 2021: 3022-3041 - Josh Alman, Virginia Vassilevska Williams:
A Refined Laser Method and Faster Matrix Multiplication. SODA 2021: 522-539 - Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
Approximate Nearest Neighbors Beyond Space Partitions. SODA 2021: 1171-1190 - Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani:
2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees. SODA 2021: 2779-2798 - Atul Singh Arora, Jérémie Roland, Chrysoula Vlachou
:
Analytic quantum weak coin flipping protocols with arbitrarily small bias. SODA 2021: 919-938 - Makis Arsenis, Odysseas Drosis, Robert Kleinberg:
Constrained-Order Prophet Inequalities. SODA 2021: 2034-2046 - Gilad Asharov, Wei-Kai Lin, Elaine Shi:
Sorting Short Keys in Circuits of Size o(n log n). SODA 2021: 2249-2268 - Sepehr Assadi, Thomas Kesselheim, Sahil Singla:
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier. SODA 2021: 653-661 - Per Austrin, Jonah Brown-Cohen, Johan Håstad:
Optimal Inapproximability with Universal Factor Graphs. SODA 2021: 434-453 - Guy Avni, Ismaël Jecker, Dorde Zikelic:
Infinite-Duration All-Pay Bidding Games. SODA 2021: 617-636 - Yossi Azar, Runtian Ren, Danny Vainstein:
The Min-Cost Matching with Concave Delays Problem. SODA 2021: 301-320 - Ainesh Bakshi, Pravesh K. Kothari:
List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time. SODA 2021: 1279-1297 - Victor Balcer, Albert Cheu, Matthew Joseph, Jieming Mao:
Connecting Robust Shuffle Privacy and Pan-Privacy. SODA 2021: 2384-2403 - Santiago R. Balseiro, Vahab S. Mirrokni, Renato Paes Leme, Song Zuo:
Non-Excludable Dynamic Mechanism Design. SODA 2021: 1357-1373 - Jess Banks, Sidhanth Mohanty, Prasad Raghavendra:
Local Statistics, Semidefinite Programming, and Community Detection. SODA 2021: 1298-1316 - Nikhil Bansal, Jatin Batra:
Non-uniform Geometric Set Cover and Scheduling on Multiple Machines. SODA 2021: 3011-3021 - Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali:
Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover. SODA 2021: 998-1005 - Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha:
Online Discrepancy Minimization for Stochastic Arrivals. SODA 2021: 2842-2861 - Paul Bastide, George Giakkoupis, Hayk Saribekyan:
Self-Stabilizing Clock Synchronization with 1-bit Messages. SODA 2021: 2154-2173 - Michael A. Bender, William Kuszmaul:
Randomized Cup Game Algorithms Against Strong Adversaries. SODA 2021: 2059-2077 - Suman K. Bera, Noujan Pashanasangi, C. Seshadhri:
Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles. SODA 2021: 2315-2332