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

The Quantum Union Bound made easy
Ryan O'Donnell and Ramgopal Venkateswaran

A Simple Algorithm for Computing the Zone of a Line in an Arrangement of Lines
Haitao Wang

Topological Art in Simple Galleries
Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider and Simon Weber

The Short-Side Advantage in Random Matching Markets
Linda Cai and Clayton Thomas

A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs
Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg and Christian Wulff-Nilsen

Understanding Nesterov's Acceleration via Proximal Point Method
Kwangjun Ahn and Suvrit Sra

Finding Relevant Points for Nearest-Neighbor Classification
David Eppstein

Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size
Edward Pyne and Salil Vadhan

An explicit vector algorithm for high-girth MaxCut
Jessica Thompson, Ojas Parekh and Kunal Marwaha

Oblivious Online Contention Resolution Schemes
Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Abner Turkieltaub, Hongxun Wu, Jinzhao Wu and Qianfan Zhang

Adversarially Robust Streaming via Dense–Sparse Trade-offs
Omri Ben-Eliezer, Talya Eden and Krzysztof Onak

Nearly Tight Bounds for Discrete Search under Outlier Noise
Anindya De, Sanjeev Khanna, Huan Li and Hesam Nikpey

Tight Bounds for Differentially Private Anonymized Histograms
Pasin Manurangsi

Parameterizing the permanent: Hardness for fixed excluded minors
Radu Curticapean and Mingji Xia

Uniformity Testing in the Shuffle Model: Simpler, Better, Faster
Clément Canonne and Hongyi Lyu

The Parameterized Complexity of the Survivable Network Design Problem
Andreas Emil Feldmann, Anish Mukherjee and Erik Jan van Leeuwen

Frequency-Domain Representation of First-Order Methods: A Simple and Robust Framework of Analysis
Ioannis Anagnostides and Ioannis Panageas

A Simple Deterministic Algorithm for Systems of Quadratic Polynomials over GF(2)
Charles Bouillaguet, Claire Delaplace and Monika Trimoska

Towards Non-Uniform k-Center with Constant Types of Radii
Xinrui Jia, Lars Rohwedder, Kshiteej Sheth and Ola Svensson

Simpler Adjacency Labeling for Planar Graphs with B-Trees
Wojciech Janczewski and Paweł Gawrychowski

Faster Exponential Algorithm for Permutation Pattern Matching
Pawel Gawrychowski and Mateusz Rzepecki

Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon and Amitai Uzrad

Parameterized Convexity Testing
Abhiruk Lahiri, Ilan Newman and Nithin Varma

A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound
Haotian Jiang and Victor Reis

A Simple Approximation Algorithm for Vector Scheduling and Applications to Stochastic Min-Norm Load Balancing
Sharat Ibrahimpur and Chaitanya Swamy