- Alkida Balliu
, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
:
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs. SODA 2023: 2632-2676 - Alkida Balliu
, Rustam Latypov, Yannic Maus, Dennis Olivetti
, Jara Uitto
:
Optimal Deterministic Massively Parallel Connectivity on Forests. SODA 2023: 2589-2631 - MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, Andreas Wiese:
Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries. SODA 2023: 2677-2727 - Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, Shachar Lovett:
Sampling Equilibria: Fast No-Regret Learning in Structured Games. SODA 2023: 3817-3855 - Soheil Behnezhad:
Dynamic Algorithms for Maximum Matching Size. SODA 2023: 129-162 - Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan:
Single-Pass Streaming Algorithms for Correlation Clustering. SODA 2023: 819-849 - Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi:
Beating Greedy Matching in Sublinear Time. SODA 2023: 3900-3945 - Xiaohui Bei, Nick Gravin, Pinyan Lu, Zhihao Gavin Tang:
Bidder Subset Selection Problem in Auction Design. SODA 2023: 3788-3801 - Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov:
Polynomial formulations as a barrier for reduction-based hardness proofs. SODA 2023: 3245-3281 - Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit:
Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Low-degree Extension in Time O(n log n) over all Finite Fields. SODA 2023: 700-737 - Ferenc Bencs, Péter Csikvári, Piyush Srivastava
, Jan Vondrák:
On complex roots of the independence polynomial. SODA 2023: 675-699 - Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini:
Tiny Pointers. SODA 2023: 477-508 - Benjamin Bergougnoux, Jan Dreier, Lars Jaffke:
A logic-based algorithmic meta-theorem for mim-width. SODA 2023: 3282-3304 - Aaron Bernstein, Nicole Wein:
Closing the Gap Between Directed Hopsets and Shortcut Sets. SODA 2023: 163-182 - Stéphane Bessy, Marin Bougeret, Dimitrios M. Thilikos, Sebastian Wiederrecht
:
Kernelization for Graph Packing Problems via Rainbow Matching. SODA 2023: 3654-3663 - Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar:
Algorithmizing the Multiplicity Schwartz-Zippel Lemma. SODA 2023: 2816-2835 - Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak:
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates. SODA 2023: 1-47 - Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc:
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. SODA 2023: 100-128 - Alexander E. Black:
Small Shadows of Lattice Polytopes. SODA 2023: 1669-1679 - Marthe Bonamy, Edouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek:
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. SODA 2023: 3006-3028 - Sander Borst, Daniel Dadush, Dan Mikulincer:
Integrality Gaps for Random Integer Programs via Discrepancy. SODA 2023: 1692-1733 - Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh
:
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms. SODA 2023: 4768-4845 - Niv Buchbinder, Joseph (Seffi) Naor, David Wajc:
Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility). SODA 2023: 2030-2068 - Nairen Cao, Jeremy T. Fineman:
Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth. SODA 2023: 4354-4372 - Jean Cardinal, Hung Phuc Hoang, Arturo I. Merino, Torsten Mütze:
Zigzagging through acyclic orientations of chordal graphs and hypergraphs. SODA 2023: 3029-3042 - Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi:
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows. SODA 2023: 2449-2488 - Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek, Sorrachai Yingchareonthawornchai:
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition. SODA 2023: 509-534 - Timothy M. Chan:
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs. SODA 2023: 1777-1805 - Timothy M. Chan, Sariel Har-Peled
:
On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings. SODA 2023: 1398-1413 - Timothy M. Chan, Da Wei Zheng
:
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures. SODA 2023: 1493-1511