Information about papers accepted for the SIAM Symposium on Simplicity in Algorithms (SOSA25)

This list is provided for reference until the online program becomes available. Title and author information appears as originally submitted; updates 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.

Sublinear-Time Algorithm for MST-Weight Revisited

Gryphon Patlin and Jan van den Brand

Simple Length-Constrained Minimum Spanning Trees

D Ellis Hershkowitz and Richard Z Huang

Validating a PTAS for Triangle-Free 2-Matching via a Simple Decomposition Theorem

Yusuke Kobayashi and Takashi Noguchi

Pure Binary Finger Search Trees

Gerth Stølting Brodal and Casper Moldrup Rysgaard

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations

William Kuszmaul

Simpler Optimal Sorting from a Directed Acyclic Graph

Ivor van der Hoog, Eva Rotenberg and Daniel Rutschmann

Trading Prophets: How to Trade Multiple Stocks Optimally

Surbhi Rajput, Ashish Chiplunkar and Rohit Vaish

A parametric version of the Hilbert Nullstellensatz

Rida Ait El Manssour, Nikhil Balaji, Klara Nosan, Mahsa Shirmohammadi and James Worrell

Dynamic Independent Set of Disks (and Hypercubes) Made Easier

Sujoy Bhore and Timothy M. Chan

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults

Elad Tzalik and Merav Parter

A Simplified Parameterized Algorithm for Directed Feedback Vertex Set

Ziliang Xiong and Mingyu Xiao

On Beating 2^n for the Closest Vector Problem

Amir Abboud and Rajendra Kumar

3SUM in Preprocessed Universes: Faster and Simpler

Shashwat Kasliwal, Adam Polak and Pratyush Sharma

Bidirectional Dijkstra’s Algorithm is Instance-Optimal

Bernhard Haeupler, Richard Hladík, Vaclav Rozhon, Robert E. Tarjan and Jakub Tětek

Spectral Sparsification by Deterministic Discrepancy Walks

Lap Chi Lau, Robert Wang and Hong Zhou

Simple Sublinear Algorithms for (\Delta+1) Vertex Coloring via Asymmetric Palette Sparsification

Sepehr Assadi and Helia Yazdanyar

The connectivity carcass of a vertex subset in a graph: both odd and even case

Surender Baswana and Abhyuday Pandey

Recursive lattice reduction---A framework for finding short lattice vectors

Divesh Aggarwal, Thomas Espitau, Spencer Peters and Noah Stephens-Davidowitz

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique

Yijia Chen, Yi Feng, Bundit Laekhanukit and Yanlin Liu

A Multilinear Johnson--Lindenstrauss Transform

Petteri Kaski, Heikki Mannila and Antonis Matakos

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths

Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe and Aurelio Sulser

Finding longer cycles via shortest colourful cycle

Andreas Björklund and Thore Husfeldt

A Simple Partially Embedded Planarity Test Based on Vertex-Addition

Simon D. Fink, Ignaz Rutter and Sandhya Thekkumpadan Puthiyaveedu

Optimal prefix/suffix queries with applications

Solon Pissis

Implementing Auction Algorithm for Efficient Matroid Intersection

Joakim Blikstad and Ta-Wei Tu

A Simple Lower Bound for Set Agreement in Dynamic Networks

Pierre Fraigniaud, Minh Hang Nguyen and Ami Paz

Testing Identity of Continuous Distributions in Polylogarithmic Space

Christian Janos Lebeda and Jakub Tetek

Only Two Shuffles Perform Card-Based Zero-Knowledge Proof for Sudoku of Any Size

Kodai Tanaka, Shun Sasaki, Kazumasa Shinagawa and Takaaki Mizuki

A Simple Algorithm for Dynamic Carpooling with Recourse

Yuval Efron, Shyamal Patel and Cliff Stein

The Quasi-probability Method and Applications for Trace Reconstruction

Ittai Rubinstein

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems

Josh Alman, Alexandr Andoni and Hengjie Zhang

Experimental Design Using Interlacing Polynomials