Data Structures and Algorithms Papers

Stochastic Matching via Local Sparsification Sara Ahmadian, Edith Cohen, Mohammad Roghani arxiv.org/abs/2605.14195 [𝚌𝚜.𝙳𝚂 𝚌𝚜.𝙻𝙶]

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model Aleksey Upirvitskiy, Aleksandr Levin arxiv.org/abs/2605.14112 [𝚌𝚜.𝙳𝚂 𝚌𝚜.𝙲𝙲]

New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions Sanjay Jain, Junqiang Peng, Frank Stephan, Haoyun Tang, Mingyu Xiao arxiv.org/abs/2605.14093 [𝚌𝚜.𝙳𝚂]

Improved Speed via Regional Fulfillment Daniel Hathcock, R. Ravi, Amitabh Sinha arxiv.org/abs/2605.14079 [𝚌𝚜.𝙳𝚂 𝚖𝚊𝚝𝚑.𝙾𝙲]

Non-Redundancy of Low-Arity Symmetric Boolean CSPs Amatya Sharma, Santhoshini Velusamy arxiv.org/abs/2605.14007 [𝚌𝚜.𝙳𝚂 𝚌𝚜.𝙲𝙲]

Clustering with Locally Bounded Ignorance Jaroslav Garvardt, Christian Komusiewicz arxiv.org/abs/2605.13917 [𝚌𝚜.𝙳𝚂 𝚌𝚜.𝙲𝙲]

Min-Max Optimization Requires Exponentially Many Queries Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender arxiv.org/abs/2605.13806 [𝚌𝚜.𝙳𝚂 𝚌𝚜.𝙲𝙲 𝚌𝚜.𝙶𝚃 𝚌𝚜.𝙻𝙶 𝚖𝚊𝚝𝚑.𝙾𝙲]

Low-Cost Arborescence Under Edge Faults Dipan Dey, Telikepalli Kavitha arxiv.org/abs/2605.13800 [𝚌𝚜.𝙳𝚂]

Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency Asaf Lev-Ran, Pavel Arkhipov, Vladimir Kolmogorov arxiv.org/abs/2605.13392 [𝚌𝚜.𝙳𝚂]

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition Peter Davies-Peck arxiv.org/abs/2605.13264 [𝚌𝚜.𝙳𝚂]

The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles Sebastian Schmidt, Juha Harviainen, Corentin Moumard, Aleksandr Politov, Francisco Sena, Alexandru I. Tomescu arxiv.org/abs/2605.13074 [𝚌𝚜.𝙳𝚂]

Time and Supply Fairness in Electricity Distribution using k-times bin packing Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-Halevi arxiv.org/abs/2605.12812 [𝚌𝚜.𝙳𝚂 𝚌𝚜.𝙼𝙰]

Thin Trees for Near Minimum Cuts Nathan Klein, Neil Olver, Zi Song Yeoh arxiv.org/abs/2605.12669 [𝚌𝚜.𝙳𝚂]

Chasing Small Sets Optimally Against Adaptive Adversaries Christian Coester, Alexa Tudose arxiv.org/abs/2605.10927 [𝚌𝚜.𝙳𝚂]

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering Fabrizio Grandoni, Anupam Gupta, Jatin Yadav arxiv.org/abs/2605.10895 [𝚌𝚜.𝙳𝚂 𝚌𝚜.𝙲𝙶]

Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes Lynn Chua, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Ziteng Sun, Chiyuan Zhang arxiv.org/abs/2605.10200 [𝚌𝚜.𝙳𝚂]

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers Yusuke Kobayashi, Takashi Noguchi arxiv.org/abs/2605.10058 [𝚌𝚜.𝙳𝚂]

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover Amey Bhangale, Yezhou Zhang arxiv.org/abs/2605.10031 [𝚌𝚜.𝙳𝚂]

Dynamic Rank, Basis, and Matching Jan van den Brand, Vishal Kumar, Daniel J. Zhang arxiv.org/abs/2605.09917 [𝚌𝚜.𝙳𝚂]

Online Steiner Forest with Recourse Yaowei Long, Sepideh Mahabadi, Sherry Sarkar, Jakub Tarnawski arxiv.org/abs/2605.09821 [𝚌𝚜.𝙳𝚂]