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

A Simple Framework for Finding Balanced Sparse Cuts via APSP
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, and Sushant Sachdeva

Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables
Josh Alman

Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs
Emmett Breen, Renee Mirka, Zichen Wang, and David P. Williamson

Gaussian Mean Testing Made Simple
Ankit Pensia, Ilias Diakonikolas, and Daniel Kane

A simple polynomial-time approximation algorithm for total variation distances between product distributions
Weiming Feng, Heng Guo, Mark Jerrum, and Jiaheng Wang

Approximate minimum cuts and their enumeration
Calvin Beideman, Karthekeyan Chandrasekaran, and Weihang Wang

A Simple Optimal Algorithm for the 2-Arm Bandit Problem
Maxime Larcher, Robert Meier, and Angelika Steger

Simple Set Sketching
Jakob Bæk Tejs Houen, Rasmus Pagh, and Stefan Walzer

Estimating the Effective Support Size in Constant Query Complexity
Shyam Narayanan and Jakub Tetek

An Optimal Lower Bound for Simplex Range Reporting
Peyman Afshani and Pingan Cheng

Proximity Search in the Greedy Tree
Oliver Chubet, Parth Parikh, Donald Sheehy, and Siddharth Sheth

On the Fine-Grained Complexity of Approximating k-Center in Sparse Graphs
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi

An Optimal Algorithm for Certifying Monotone Functions
Meghal Gupta and Naren Manoj

A Simple Combinatorial Algorithm for Robust Matroid Center
Georg Anegg, Laura Vargas Koch, and Rico Zenklusen

Simpler and faster algorithms for detours in planar digraphs
Meike Hatzel, Konrad Majewski, Michał Pilipczuk, and Marek Sokołowski

Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps
Volkan Cevher, Georgios Piliouras, Ryann Sim, and Stratis Skoulakis

A Simple Algorithm for Submodular Minimum Linear Ordering
Dor Katzelnick and Roy Schwartz

A Tight Analysis of Hutchinson's Diagonal Estimator
Prathamesh Dharangutte and Christopher Musco

A Simple Deterministic Distributed Low-Diameter Clustering
Vaclav Rozhon, Bernhard Haeupler and Christoph Grunau

Simplified Prophet Inequalities for Combinatorial Auctions
Alexander Braun and Thomas Kesselheim

Derandomization of Cell Sampling
Alexander Golovnev, Tom Gur, and Igor Shinkar

Minimum Cost Adaptive Submodular Cover
Yubing Cui and Viswanath Nagarajan

An EPTAS for Budgeted Matroid Independent Set
Ilan Doron, Ariel Kulik, and Hadas Shachnai

Sinkless Orientation Made Simple
Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela, and Jara Uitto

Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information
Richard Santiago, Ivan Sergeev, and Rico Zenklusen

Voting algorithms for Unique Games on complete graphs
Antoine Méot, Arnaud de Mesmay, Moritz Muehlenthaler, and Alantha Newman

A Local Search-Based Approach for Set Covering
Anupam Gupta, Euiwoong Lee, and Jason Li

Capacitated Vehicle Routing in Graphic Metrics
Tobias Mömke and Hang Zhou

Optimal resizable arrays
Robert E. Tarjan and Uri Zwick

Splay Top Trees
Jacob Holm, Eva Rotenberg, and Alice Ryhl

Sampling an Edge in $O(n/\sqrt{m} + \log \varepsilon^{-1})$ Time via Bernoulli Trial Simulation
Talya Eden, Shyam Narayanan, and Jakub Tetek

An Improved Online Reduction from PAC Learning to Mistake-Bounded Learning
Lucas Gretta and Eric Price

Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching
Gergely Csáji, Tamás Király, and Yu Yokoi

Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)
Binghui Peng and Aviad Rubinstein

Tight Bounds for Vertex Connectivity in Dynamic Streams
Vihan Shah and Sepehr Assadi