arXiv cs.DS Data Structures and Algorithms

Zichun Ye, Runqi Wang, Xutong Liu, Shuai Li: Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits https://arxiv.org/abs/2508.06247 https://arxiv.org/pdf/2508.06247 https://arxiv.org/html/2508.06247

Beisegel, Chiarelli, K\"ohler, Krnc, Milani\v{c}, Piva\v{c}, Scheffler, Strehler: Sandwich Monotonicity and the Recognition of Weighted Graph Classes https://arxiv.org/abs/2508.06216 https://arxiv.org/pdf/2508.06216 https://arxiv.org/html/2508.06216

Tyler Chen, Ethan N. Epperly, Raphael A. Meyer, Christopher Musco, Akash Rao: Does block size matter in randomized block Krylov low-rank approximation? https://arxiv.org/abs/2508.06486 https://arxiv.org/pdf/2508.06486 https://arxiv.org/html/2508.06486

Dan Johnson, Michael Levet, Petr Vojt\v{e}chovsk\'y, Brett Widholm: On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions https://arxiv.org/abs/2508.06478 https://arxiv.org/pdf/2508.06478 https://arxiv.org/html/2508.06478

Akash Pareek, Supratim Shit: A Simple PTAS for Weighted $k$-means and Sensor Coverage https://arxiv.org/abs/2508.06460 https://arxiv.org/pdf/2508.06460 https://arxiv.org/html/2508.06460

Theresa Pollinger, Masado Ishii, Jens Domke: The Beauty of Anisotropic Mesh Refinement: Omnitrees for Efficient Dyadic Discretizations https://arxiv.org/abs/2508.06316 https://arxiv.org/pdf/2508.06316 https://arxiv.org/html/2508.06316

Romain Bourneuf, Tim Planken: A Structural Linear-Time Algorithm for Computing the Tutte Decomposition https://arxiv.org/abs/2508.06212 https://arxiv.org/pdf/2508.06212 https://arxiv.org/html/2508.06212

Chris Cama\~no, Raphael A. Meyer, Kevin Shu: Debiasing Polynomial and Fourier Regression https://arxiv.org/abs/2508.05920 https://arxiv.org/pdf/2508.05920 https://arxiv.org/html/2508.05920

[2025-08-11 Mon (UTC), 6 new articles found for csDS Data Structures and Algorithms]

Serge Gaspers, Zixu He, Simon Mackenzie: NP-Hardness and ETH-Based Inapproximability of Communication Complexity via Relaxed Interlacing https://arxiv.org/abs/2508.05597 https://arxiv.org/pdf/2508.05597 https://arxiv.org/html/2508.05597

Abigail Gentle: Necessity of Block Designs for Optimal Locally Private Distribution Estimation https://arxiv.org/abs/2508.05110 https://arxiv.org/pdf/2508.05110 https://arxiv.org/html/2508.05110

Yue Wu, Binghong Li, Kathleen Chang, Shruti Puri, Lin Zhong: Minimum-Weight Parity Factor Decoder for Quantum Error Correction https://arxiv.org/abs/2508.04969 https://arxiv.org/pdf/2508.04969 https://arxiv.org/html/2508.04969

Jingyang Zhao, Mingyu Xiao: An Improved Approximation Algorithm for the Capacitated Arc Routing Problem https://arxiv.org/abs/2508.05471 https://arxiv.org/pdf/2508.05471 https://arxiv.org/html/2508.05471

Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale: Parameterized complexity of isometric path partition: treewidth and diameter https://arxiv.org/abs/2508.05448 https://arxiv.org/pdf/2508.05448 https://arxiv.org/html/2508.05448

Joyentanuj Das, Suranjan De, He Sun: Online Sparsification of Bipartite-Like Clusters in Graphs https://arxiv.org/abs/2508.05437 https://arxiv.org/pdf/2508.05437 https://arxiv.org/html/2508.05437

Fangjian Shen, Yicheng Zheng, Wushao Wen, Hankz Hankui Zhuo: Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size https://arxiv.org/abs/2508.05351 https://arxiv.org/pdf/2508.05351 https://arxiv.org/html/2508.05351

Ziad Ismaili Alaoui, Detlef Plump, Sebastian Wild: Space-Efficient Hierholzer: Eulerian Cycles in O(m) Time and O(n) Space https://arxiv.org/abs/2508.05251 https://arxiv.org/pdf/2508.05251 https://arxiv.org/html/2508.05251

Solon P. Pissis: Text Indexing and Pattern Matching with Ephemeral Edits https://arxiv.org/abs/2508.05124 https://arxiv.org/pdf/2508.05124 https://arxiv.org/html/2508.05124

Sunny Atalig, Marek Chrobak: A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths https://arxiv.org/abs/2508.04872 https://arxiv.org/pdf/2508.04872 https://arxiv.org/html/2508.04872

Thejas Radhika Sajith: Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space https://arxiv.org/abs/2508.04726 https://arxiv.org/pdf/2508.04726 https://arxiv.org/html/2508.04726

[2025-08-08 Fri (UTC), 8 new articles found for csDS Data Structures and Algorithms]

Eric Ma, Tselil Schramm: Polynomial-time sampling despite disorder chaos https://arxiv.org/abs/2508.04133 https://arxiv.org/pdf/2508.04133 https://arxiv.org/html/2508.04133

Nikhil Bansal, Haotian Jiang: Decoupling via Affine Spectral-Independence: Beck-Fiala and Koml\'os Bounds Beyond Banaszczyk https://arxiv.org/abs/2508.03961 https://arxiv.org/pdf/2508.03961 https://arxiv.org/html/2508.03961

Chi-Yeh Chen: Approximation Algorithms for Scheduling Crowdsourcing Tasks in Mobile Social Networks https://arxiv.org/abs/2508.04159 https://arxiv.org/pdf/2508.04159 https://arxiv.org/html/2508.04159

Ryotaro Sato, Yutaro Yamaguchi: Exact Matching in Matrix Multiplication Time https://arxiv.org/abs/2508.04081 https://arxiv.org/pdf/2508.04081 https://arxiv.org/html/2508.04081

Joshua Petrack, David Doty: Exactly simulating stochastic chemical reaction networks in sub-constant time per reaction https://arxiv.org/abs/2508.04079 https://arxiv.org/pdf/2508.04079 https://arxiv.org/html/2508.04079

Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Wale\'n, Wiktor Zuba: Counting Distinct Square Substrings in Sublinear Time https://arxiv.org/abs/2508.03930 https://arxiv.org/pdf/2508.03930 https://arxiv.org/html/2508.03930

Joshua Stapleton: A 60-Addition, Rank-23 Scheme for Exact 3x3 Matrix Multiplication https://arxiv.org/abs/2508.03857 https://arxiv.org/pdf/2508.03857 https://arxiv.org/html/2508.03857

[2025-08-07 Thu (UTC), 5 new articles found for csDS Data Structures and Algorithms]

Ben Bals, Sebastiaan van Krieken, Solon P. Pissis, Leen Stougie, Hilde Verbeek: When is String Reconstruction using de Bruijn Graphs Hard? https://arxiv.org/abs/2508.03433 https://arxiv.org/pdf/2508.03433 https://arxiv.org/html/2508.03433