SOSA24 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.

An Alternate Proof of Near-Optimal Light Spanners
Greg Bodwin

Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover
Nate Veldt

When Stochastic Rewards Reduce to Deterministic Rewards in Online Bipartite Matching
Rajan Udwani

On Embeddings that Preserve the Relative Order of Distances for Triplets, Terminals \& Top-$k$ Nearest Neighbors
Vaggos Chatziafratis and Piotr Indyk

A Simple (1-eps)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
Sepehr Assadi

Simple Analysis of Priority Sampling
Majid Daliri, Juliana Freire, Christopher Musco, Aécio Santos and Haoxiang Zhang

Improved Algorithms for Integer Complexity
Qizheng He

A CS guide to the quantum singular value transformation
Ewin Tang and Kevin Tian

Minimum cost paths for electric cars
Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Mikkel Thorup and Uri Zwick

Revisiting Random Points: Combinatorial Complexity and Algorithms
Elfarouk Harb and Sariel Har-Peled

Fully Dynamic $k$-Center in Low Dimensions via Approximate Furthest Neighbors
Jinxiang Gan and Mordecai Golin

Listing 6-Cycles
Ce Jin, Virginia Vassilevska Williams and Renfei Zhou

An Enumerative Perspective on Connectivity
Shyan Akmal

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
Karthik C. S., Daniel Marx, Marcin Pilipczuk and Uéverton Souza

Simple Linear-Size Additive Emulators
Gary Hoppenworth

The greedy algorithm for SCS is a $\frac 12$-approximation in terms of compression: a simple proof
Pavel Kalugin and Maksim Nikolaev

Modern Hashing Made Simple
Michael A. Bender, Martin Farach-Colton, John Kuszmaul and William Kuszmaul

Simpler constant factor approximation algorithms for weighted flow time -- now for any p-norm
Alexander Armbruster, Lars Rohwedder and Andreas Wiese

Quantum Logspace Computations are Verifiable
Uma Girish, Ran Raz and Wei Zhan

Detecting points in integer cones of polytopes is double-exponentially hard
Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michał Pilipczuk and Marek Sokołowski

Convex Approximation and the Hilbert Geometry
Ahmed Abdelkader and David Mount

Simple and Optimal Online Bipartite Edge Coloring
Joakim Blikstad, Ola Svensson, Radu Vintan and David Wajc

Simpler Reductions from Exact Triangle
Timothy M. Chan and Yinzhan Xu

The Public University Secretary Problem
Benjamin Moseley, Heather Newman and Kirk Pruhs

Simple and Faster Algorithms for Knapsack
Qizheng He and Zhean Xu

Sorting Signed Permutations by Reversals in Nearly-Linear Time
Bartlomiej Dudek, Pawel Gawrychowski and Tatiana Starikovskaya

If Edge Coloring is hard under SETH, then SETH is false
Alexander Kulikov and Ivan Mikhailin

A General Technique for Searching in Implicit Sets via Function Inversion
Boris Aronov, Jean Cardinal, Justin Dallant and John Iacono

SSD Wear Leveling with Optimal Guarantees
Tomer Lange, Seffi Naor and Gala Yadgar

Finding the saddlepoint faster than sorting
Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma and Sebastian Wild

Simple and tight complexity lower bounds for solving Rabin games
Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk, Ueverton Souza and K. S. Thejaswini

Contention Resolution for the $\ell$-fold union of a matroid via the correlation gap
Chandra Chekuri, Junkai Song and Weizhong Zhang

Simpler Distribution Testing with Little Memory
Clément Canonne and Joy Qiping Yang

USSR is in P/poly
Nikhil Balaji and Samir Datta

Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs
Sven Jäger and Philipp Warode

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
Phevos Paschalidis and Ashley Zhuang

Insertion-Only Dynamic Connectivity in General Disk Graphs
Haim Kaplan, Katharina Klost, Kristin Knorr, Wolfgang Mulzer and Liam Roditty