SIAM Symposium on Simplicity in Algorithms (SOSA26)

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.

Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling

Felix Zhou

A Simpler Approximation Algorithm for MAX-k-SAT

Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gal, Norbert Schuch, Suguru Tamaki

Semi-Robust Communication Complexity of Maximum Matching

Gabriel Cipriani Huete, Adithya Diddapur, Pavel Dvorak, Christian Konrad

Tight Lower Bound for Multicolor Discrepancy

Pasin Manurangsi, Raghu Meka

Maximal Palindromes in MPC: Simple and Optimal

Solon Pissis

The Harmonic Policy for Online Buffer Sharing is $(2 + \ln n)$-Competitive: A Simple Proof

Vamsi Addanki, Julien Dallot, Leon Kellerhals, Maciej Pacut, Stefan Schmid

A Linear-Time Algorithm for the MCS End-Vertex Problem on Chordal Graphs: A Bonus-Driven Search Strategy

Guozhen Rong, Biao Yuan, Yongjie Yang, Zhen Zhang

A Levelset Algorithm for 3D-Tarski

Sebastian Haslebacher, Jonas Lill

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles

Shuyi Yan

A Novel Reduction from #SAT to #2SAT Based on Symmetry: Simply Drop the Large Clauses

Max Bannach, Erik Demaine, Timothy Gomez, Markus Hecher

Computing the Fréchet Distance When Just One Curve is c-Packed: A Simple Almost-Tight Algorithm

Jacobus Conradi, Ivor van der Hoog, Thijs van der Horst, Tim Ophelders

The Sparsification Lemma via Measure and Conquer

Daniel Lokshtanov, Saket Saurabh, Jie Xue

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates

Pachara Sawettamalya, Huacheng Yu

An Exact Algorithm for the Unanimous Vote Problem

Feyza Duman Keles, Lisa Hellerstein, Kunal Marwaha, Christopher Musco, Xinchen Yang

A note on Ordered Ruzsa-Szemerédi graphs

Kevin Pratt

Tree Violation Distance under Constraints

Debarati Das, Evangelos Kipouridis, Joachim Spoerhase

Simple Average-case Analysis of Recursive Randomized Greedy MIS

Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović

Reducing Shortcut and Hopset Constructions to Shallow Graphs

Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak

The k-Fold Matroid Secretary Problem

Frederick Qiu, Kevin Hua, Rishi Gujjar, Robert Kleinberg

Yet Another Proof that BPP ⊆ PH

Ilya Volkovich

Trading Prophets with Initial Capital

Yossi Azar, Niv Buchbinder, Roie Levin, Or Vardi

Efficient derandomization of differentially private counting queries

Surendra Ghentiyala

Simple Length-Constrained Expander Decompositions

Greg Bodwin, Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan

Static Pricing for Single Sample Multi-unit Prophet Inequalities

Pranav Nuti, Peter Westbrook

Competitive Online Transportation Simplified

Stephen Arndt, Kirk Pruhs, Benjamin Moseley, Marc Uetz

The Road to the Closest Point is Paved by Good Neighbors

Sariel Har-Peled, Benjamin Raichel, Eliot Robson

A Learning Perspective on Random-Order Covering Problems

Anupam Gupta, Marco Molinaro, Matteo Russo

Space-Efficient Hierholzer: Eulerian Cycles in O(m) Time and O(n) Space

Ziad Ismaili Alaoui, Sebastian Wild

Redistricting in Triangular and Square Grids

Hugo Akitaya, Kyle Dituro, Andrei Gonczi, Matias Korman, Diane Souvaine, Frederick Stock, Csaba Toth

Debiasing Polynomial and Fourier Regression

Chris Camaño, Kevin Shu, Raphael Meyer

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs

Olivier Fischer, Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai

Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing

Zongbo Bao, Yuxuan Liu, Penghui Yao, Zekun Ye, Jialin Zhang

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP

Morteza Alimi, Niklas Dahlmeier, Tobias Mömke, Philipp Pabst, Laura Vargas Koch

Simple Algorithms for Fully Dynamic Edge Connectivity

Yotam Kenneth-Mordoch, Robert Krauthgamer

A Simple Analysis of Ranking in General Graphs

Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu

Unsplittable Cost Flows from Unweighted Error-Bounded Variants

Chaitanya Swamy, Vera Traub, Laura Vargas Koch, Rico Zenklusen

Text Indexing and Pattern Matching with Ephemeral Edits