SOSA

Publications

2024

Ahmed Abdelkader, David M. Mount
Convex Approximation and the Hilbert Geometry. SOSA (2024)
Alexander S. Kulikov, Ivan Mihajlin
If Edge Coloring is Hard under SETH, then SETH is False. SOSA (2024)
Nate Veldt
Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover. SOSA (2024)
Gary Hoppenworth
Simple Linear-Size Additive Emulators. SOSA (2024)
Sven Jäger, Philipp Warode
Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs. SOSA (2024)
Qizheng He
Improved Algorithms for Integer Complexity. SOSA (2024)
Chandra Chekuri, Junkai Song, Weizhong Zhang
-fold union of a matroid via the correlation gap. SOSA (2024)
Sepehr Assadi
)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching. SOSA (2024)
Tomer Lange, Joseph (Seffi) Naor, Gala Yadgar
SSD Wear Leveling with Optimal Guarantees. SOSA (2024)
Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michal Pilipczuk, Marek Sokolowski
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard. SOSA (2024)
Rajan Udwani
When Stochastic Rewards Reduce to Deterministic Rewards in Online Bipartite Matching. SOSA (2024)
Antonio Casares, Marcin Pilipczuk, Michal Pilipczuk, Uéverton S. Souza, K. S. Thejaswini
Simple and tight complexity lower bounds for solving Rabin games. SOSA (2024)
Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Mikkel Thorup, Uri Zwick
Minimum-cost paths for electric cars. SOSA (2024)
Ewin Tang, Kevin Tian
A CS guide to the quantum singular value transformation. SOSA (2024)
Boris Aronov, Jean Cardinal, Justin Dallant, John Iacono
A General Technique for Searching in Implicit Sets via Function Inversion. SOSA (2024)
Clément L. Canonne, Joy Qiping Yang
Simpler Distribution Testing with Little Memory. SOSA (2024)
Shyan Akmal
An Enumerative Perspective on Connectivity. SOSA (2024)
Haim Kaplan, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roditty
Insertion-Only Dynamic Connectivity in General Disk Graphs. SOSA (2024)
Majid Daliri, Juliana Freire, Christopher Musco, Aécio S. R. Santos, Haoxiang Zhang
Simple Analysis of Priority Sampling. SOSA (2024)
Benjamin Moseley, Heather Newman, Kirk Pruhs
The Public University Secretary Problem. SOSA (2024)
Qizheng He, Zhean Xu
Simple and Faster Algorithms for Knapsack. SOSA (2024)
Vaggos Chatziafratis, Piotr Indyk
Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors. SOSA (2024)
2024 Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, VA, USA, January 8-10, 2024 SOSA (2024)
Ce Jin, Virginia Vassilevska Williams, Renfei Zhou
Listing 6-Cycles. SOSA (2024)
Timothy M. Chan, Yinzhan Xu
Simpler Reductions from Exact Triangle. SOSA (2024)
Nikhil Balaji, Samir Datta
USSR is in P/poly. SOSA (2024)
Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, Sebastian Wild
Finding the saddlepoint faster than sorting. SOSA (2024)
Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya
Sorting Signed Permutations by Reversals in Nearly-Linear Time. SOSA (2024)
Phevos Paschalidis, Ashley Zhuang
Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem. SOSA (2024)
Greg Bodwin
An Alternate Proof of Near-Optimal Light Spanners. SOSA (2024)
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
-norm. SOSA (2024)
Pavel E. Kalugin, Maksim S. Nikolaev
The greedy algorithm for the Shortest Common Superstring problem is a ½-approximation in terms of compression: a simple proof. SOSA (2024)
Jinxiang Gan, Mordecai J. Golin
-Center in Low Dimensions via Approximate Furthest Neighbors. SOSA (2024)
Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. SOSA (2024)
Sariel Har-Peled, Elfarouk Harb
Revisiting Random Points: Combinatorial Complexity and Algorithms. SOSA (2024)
Uma Girish, Ran Raz, Wei Zhan
Quantum Logspace Computations are Verifiable. SOSA (2024)
Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul
Modern Hashing Made Simple. SOSA (2024)
Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
Simple and Asymptotically Optimal Online Bipartite Edge Coloring. SOSA (2024)

2023