SOSA

Keyphrases

Publications

2023

Meike Hatzel, Konrad Majewski, Michal Pilipczuk, Marek Sokolowski
Simpler and faster algorithms for detours in planar digraphs. SOSA (2023)
Alexander Golovnev, Tom Gur, Igor Shinkar
Derandomization of Cell Sampling. SOSA (2023)
Richard Santiago, Ivan Sergeev, Rico Zenklusen
Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information. SOSA (2023)
Prathamesh Dharangutte, Christopher Musco
A Tight Analysis of Hutchinson's Diagonal Estimator. SOSA (2023)
Tobias Mömke, Hang Zhou
Capacitated Vehicle Routing in Graphic Metrics. SOSA (2023)
Volkan Cevher, Georgios Piliouras, Ryann Sim, Stratis Skoulakis
Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps. SOSA (2023)
Emmett Breen, Renee Mirka, Zichen Wang, David P. Williamson
-MST Problem in Graphs. SOSA (2023)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
-Center in Sparse Graphs. SOSA (2023)
Jakob Bæk Tejs Houen, Rasmus Pagh, Stefan Walzer
Simple Set Sketching. SOSA (2023)
Robert E. Tarjan, Uri Zwick
Optimal resizable arrays. SOSA (2023)
Václav Rozhon, Bernhard Haeupler, Christoph Grunau
A Simple Deterministic Distributed Low-Diameter Clustering. SOSA (2023)
Yubing Cui, Viswanath Nagarajan
Minimum Cost Adaptive Submodular Cover. SOSA (2023)
Oliver A. Chubet, Parth Parikh, Donald R. Sheehy, Siddharth Sheth
Proximity Search in the Greedy Tree. SOSA (2023)
Jacob Holm, Eva Rotenberg, Alice Ryhl
Splay Top Trees. SOSA (2023)
Shyam Narayanan, Jakub Tetek
Estimating the Effective Support Size in Constant Query Complexity. SOSA (2023)
Weiming Feng, Heng Guo, Mark Jerrum, Jiaheng Wang
A simple polynomial-time approximation algorithm for the total variation distance between two product distributions. SOSA (2023)
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
A Simple Framework for Finding Balanced Sparse Cuts via APSP. SOSA (2023)
Binghui Peng, Aviad Rubinstein
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window). SOSA (2023)
Talya Eden, Shyam Narayanan, Jakub Tetek
Sampling an Edge in Sublinear Time Exactly and Optimally. SOSA (2023)
Alexander Braun, Thomas Kesselheim
Simplified Prophet Inequalities for Combinatorial Auctions. SOSA (2023)
Dor Katzelnick, Roy Schwartz
A Simple Algorithm for Submodular Minimum Linear Ordering. SOSA (2023)
Anupam Gupta, Euiwoong Lee, Jason Li
A Local Search-Based Approach for Set Covering. SOSA (2023)
Georg Anegg, Laura Vargas Koch, Rico Zenklusen
A Simple Combinatorial Algorithm for Robust Matroid Center. SOSA (2023)
Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela, Jara Uitto
Sinkless Orientation Made Simple. SOSA (2023)
Lucas Gretta, Eric Price
An Improved Online Reduction from PAC Learning to Mistake-Bounded Learning. SOSA (2023)
Josh Alman
Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables. SOSA (2023)
Ilan Doron Arad, Ariel Kulik, Hadas Shachnai
An EPTAS for Budgeted Matroid Independent Set. SOSA (2023)
Sepehr Assadi, Vihan Shah
Tight Bounds for Vertex Connectivity in Dynamic Streams. SOSA (2023)
Peyman Afshani, Pingan Cheng
An Optimal Lower Bound for Simplex Range Reporting. SOSA (2023)
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
Gaussian Mean Testing Made Simple. SOSA (2023)
Maxime Larcher, Robert Meier, Angelika Steger
A Simple Optimal Algorithm for the 2-Arm Bandit Problem. SOSA (2023)
Antoine Méot, Arnaud de Mesmay, Moritz Mühlenthaler, Alantha Newman
Voting algorithms for unique games on complete graphs. SOSA (2023)
Gergely Csáji, Tamás Király, Yu Yokoi
Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching. SOSA (2023)
Calvin Beideman, Karthekeyan Chandrasekaran, Weihang Wang
Approximate minimum cuts and their enumeration. SOSA (2023)
2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023 SOSA (2023)
Meghal Gupta, Naren Sarayu Manoj
An Optimal Algorithm for Certifying Monotone Functions. SOSA (2023)

2022