Data Structures and Algorithms

Authors and titles for recent submissions

• Thu, 25 Sep 2025
• Wed, 24 Sep 2025
• Tue, 23 Sep 2025
• Mon, 22 Sep 2025
• Fri, 19 Sep 2025

See today's new changes

Wed, 24 Sep 2025 (showing 4 of 4 entries )

[14] arXiv:2509.19242 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Linear Regression under Missing or Corrupted Coordinates Show Chinese title

Title: 缺失或损坏坐标下的线性回归

Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Jasper C.H. Lee, Thanasis Pittas

Subjects: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG) ; Statistics Theory (math.ST) ; Machine Learning (stat.ML)

[15] arXiv:2509.19021 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Optimization of Base-n Radix Sort for Skewed Datasets Show Chinese title

Title: 偏斜数据集的基数排序优化

Atharv Pandey, Lakshmanan Kuppusamy

Comments: 17 pages including Appendix

Subjects: Data Structures and Algorithms (cs.DS)

[16] arXiv:2509.18984 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: GraphBLAS Mathematical Opportunities: Parallel Hypersparse, Matrix Based Graph Streaming, and Complex-Index Matrices Show Chinese title

Title: GraphBLAS数学机会：并行超稀疏、基于矩阵的图流和复数索引矩阵

Hayden Jananthan, Jeremy Kepner, Michael Jones, Vijay Gadepally, Michael Houle, Peter Michaleas, Chasen Milner, Alex Pentland

Comments: HPEC 2025

Subjects: Data Structures and Algorithms (cs.DS)

[17] arXiv:2509.18936 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Precoloring extension with demands on paths Show Chinese title

Title: 带有路径需求的预着色扩展

Arun Kumar Das, Michal Opler, Tomáš Valla

Comments: Full version of paper accepted to ISAAC

Subjects: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC)

Tue, 23 Sep 2025 (showing 11 of 11 entries )

[18] arXiv:2509.17819 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Theory Meets Practice for Bit Vectors Supporting Rank and Select Show Chinese title

Title: 理论与实践结合的位向量支持秩和选择

Florian Kurpicz, Niccolò Rigi-Luperti, Peter Sanders

Subjects: Data Structures and Algorithms (cs.DS)

[19] arXiv:2509.17269 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries Show Chinese title

Title: 带有验证查询的任意主导噪声下的分布测试

Hadley Black, Christopher Ye

Subjects: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM)

[20] arXiv:2509.17226 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Distance Approximating Minors for Planar and Minor-Free Graphs Show Chinese title

Title: 平面图和无小图的图的距离逼近小式

Hsien-Chih Chang, Jonathan Conroy

Comments: 32 pages, 6 figures. Accepted to FOCS 2025

Subjects: Data Structures and Algorithms (cs.DS) ; Computational Geometry (cs.CG) ; Discrete Mathematics (cs.DM)

[21] arXiv:2509.17029 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Optimal 4-Approximation for the Correlated Pandora's Problem Show Chinese title

Title: 相关潘多拉问题的最优4-近似解

Nikhil Bansal, Zhiyi Huang, Zixuan Zhu

Comments: to appear in FOCS 2025

Subjects: Data Structures and Algorithms (cs.DS)

[22] arXiv:2509.16815 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Quadratic Kernel for Cliques or Trees Vertex Deletion Show Chinese title

Title: 用于团或树顶点删除的二次核

Soh Kumabe

Comments: ISAAC 2025

Subjects: Data Structures and Algorithms (cs.DS)

[23] arXiv:2509.16801 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Sublinear Time Quantum Sensitivity Sampling Show Chinese title

Title: 子线性时间量子敏感性采样

Zhao Song, David P. Woodruff, Lichen Zhang

Subjects: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG) ; Quantum Physics (quant-ph)

[24] arXiv:2509.17926 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Sketching approximations and LP approximations for finite CSPs are related Show Chinese title

Title: 有限CSP的草图近似和LP近似是相关的

Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy

Subjects: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS)

[25] arXiv:2509.17591 (cross-list from cs.IT) [cn-pdf, pdf, html, other]

Title: Hyperbolic Sets in Incomplete Tables Show Chinese title

Title: 双曲集在不完整表中

J. J. Bernal, J. J. Simón

Subjects: Information Theory (cs.IT) ; Data Structures and Algorithms (cs.DS)

[26] arXiv:2509.16915 (cross-list from math.OC) [cn-pdf, pdf, html, other]

Title: Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming Show Chinese title

Title: 欧几里得乔丹代数的差分隐私及其在私有对称锥规划中的应用

Zhao Song, Jianfei Xue, Lichen Zhang

Comments: NeurIPS 2025

Subjects: Optimization and Control (math.OC) ; Cryptography and Security (cs.CR) ; Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG)

[27] arXiv:2509.16407 (cross-list from cs.DC) [cn-pdf, pdf, other]

Title: WarpSpeed: A High-Performance Library for Concurrent GPU Hash Tables Show Chinese title

Title: WarpSpeed：用于并发GPU哈希表的高性能库

Hunter McCoy, Prashant Pandey

Subjects: Distributed, Parallel, and Cluster Computing (cs.DC) ; Data Structures and Algorithms (cs.DS)

[28] arXiv:2509.16405 (cross-list from q-bio.PE) [cn-pdf, pdf, html, other]

Title: Ordered Leaf Attachment (OLA) Vectors can Identify Reticulation Events even in Multifurcated Trees Show Chinese title

Title: 有序叶附着（OLA）向量可以在多歧树中识别网状事件

Alexey Markin, Tavis K. Anderson

Comments: 18 pages, 4 figures

Subjects: Populations and Evolution (q-bio.PE) ; Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO)

Mon, 22 Sep 2025 (showing 9 of 9 entries )

[29] arXiv:2509.16194 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Clustering with Set Outliers and Applications in Relational Clustering Show Chinese title

Title: 带有集合异常值的聚类及其在关系聚类中的应用

Vaishali Surianarayanan, Neeraj Kumar, Stavros Sintos

Subjects: Data Structures and Algorithms (cs.DS) ; Databases (cs.DB)

[30] arXiv:2509.16180 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph Show Chinese title

Title: 通过Scheffe图进行查询高效的局部私有假设选择

Gautam Kamath, Alireza F. Pour, Matthew Regehr, David P. Woodruff

Subjects: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG) ; Machine Learning (stat.ML)

[31] arXiv:2509.16171 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Analyzing and improving a classical Betti number estimation algorithm Show Chinese title

Title: 分析和改进经典的贝蒂数估计算法

Julien Sorci

Subjects: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM) ; Quantum Physics (quant-ph)

[32] arXiv:2509.16143 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: On the Structural Parameterizations of 2-Club with Triangle Constraints Show Chinese title

Title: 关于带有三角形约束的2-俱乐部的结构参数化

Ashwin Jacob, Diptapriyo Majumdar, Raghav Sakhuja

Comments: 1 figure, 31 pages

Subjects: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM)

[33] arXiv:2509.16135 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Constant time enumeration of perfect bipartite matchings Show Chinese title

Title: 完美二部图匹配的常数时间枚举

Jiří Fink

Comments: 40 pages, 6 figures

Subjects: Data Structures and Algorithms (cs.DS)

[34] arXiv:2509.15531 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization Show Chinese title

Title: 基于图的近似最近邻搜索重新审视：理论分析与优化

Xinran Ma, Zhaoqi Zhou, Chuan Zhou, Qi Meng, Zaijiu Shang, Guoliang Li, Zhiming Ma

Subjects: Data Structures and Algorithms (cs.DS)

[35] arXiv:2509.16008 (cross-list from cs.CG) [cn-pdf, pdf, html, other]

Title: A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions Show Chinese title

Title: 最大范围和的一束结果：通用技术和难解性归约

Rachana Gusain, Saladi Rahul, Aditya Subramanian

Comments: Accepted for publication at Principles of Database Systems (PODS) 2026

Subjects: Computational Geometry (cs.CG) ; Data Structures and Algorithms (cs.DS)

[36] arXiv:2509.15458 (cross-list from math.CO) [cn-pdf, pdf, html, other]

Title: Tree-independence number VI. Thetas and pyramids Show Chinese title

Title: 树独立数 VI. θ和金字塔

Maria Chudnovsky, Julien Codsi

Comments: 27 pages, 6 figures

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS)

[37] arXiv:2509.15294 (cross-list from quant-ph) [cn-pdf, pdf, html, other]

Title: Classical and Quantum Heuristics for the Binary Paint Shop Problem Show Chinese title

Title: 经典与量子启发式方法在二进制涂装车间问题中的应用

V Vijendran, Dax Enshan Koh, Ping Koy Lam, Syed M Assad

Comments: 30 Pages and 3 Figures

Subjects: Quantum Physics (quant-ph) ; Data Structures and Algorithms (cs.DS) ; Emerging Technologies (cs.ET) ; Optimization and Control (math.OC)

Fri, 19 Sep 2025 (showing 11 of 11 entries )

[38] arXiv:2509.15137 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Balanced Spanning Tree Distributions Have Separation Fairness Show Chinese title

Title: 平衡生成树分布具有分离公平性

Harry Chen, Kamesh Munagala, Govind S. Sankar

Subjects: Data Structures and Algorithms (cs.DS) ; Computers and Society (cs.CY)

[39] arXiv:2509.15080 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs Show Chinese title

Title: 树和二分图中的捆绑最小和着色

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Comments: An extended abstract of this paper will appear in Proceedings of 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Subjects: Data Structures and Algorithms (cs.DS)

[40] arXiv:2509.14993 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Fast and Optimal Incremental Parametric Procedure for the Densest Subgraph Problem: An Experimental Study Show Chinese title

Title: 快速且最优的密集子图问题增量参数化过程：一项实验研究

Dorit S. Hochbaum, Ayleen Irribarra-Cortés, Olivier Goldschmidt, Roberto Asín-Achá

Subjects: Data Structures and Algorithms (cs.DS)

[41] arXiv:2509.14898 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Streaming periodicity with mismatches, wildcards, and edits Show Chinese title

Title: 带有错位、通配符和编辑的流式周期性

Taha El Ghazi, Tatiana Starikovskaya

Comments: Accepted to ISAAC 2025

Subjects: Data Structures and Algorithms (cs.DS)

[42] arXiv:2509.14588 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions Show Chinese title

Title: 高效算法用于不相交最短路径问题及其扩展

Keerti Choudhary, Amit Kumar, Lakshay Saggi

Subjects: Data Structures and Algorithms (cs.DS)

[43] arXiv:2509.14489 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum Show Chinese title

Title: 克罗内克幂，正交向量和渐近谱

Josh Alman, Baitian Li

Comments: 57 pages, to appear in FOCS 2025

Subjects: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC)

[44] arXiv:2509.14433 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Fast and Compact Sketch-Based Dynamic Connectivity Show Chinese title

Title: 快速且紧凑的基于草图的动态连通性

Quinten De Man, Qamber Jafri, Daniel Delayo, Evan T. West, Michael A. Bender, David Tench

Subjects: Data Structures and Algorithms (cs.DS)

[45] arXiv:2509.14334 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting Show Chinese title

Title: 归一化平方根：差分隐私持续计数的更紧矩阵分解界限

Monika Henzinger, Nikita P. Kalinin, Jalaj Upadhyay

Subjects: Data Structures and Algorithms (cs.DS) ; Cryptography and Security (cs.CR) ; Machine Learning (cs.LG)

[46] arXiv:2509.15069 (cross-list from eess.SP) [cn-pdf, pdf, html, other]

Title: Efficient Computation of Time-Index Powered Weighted Sums Using Cascaded Accumulators Show Chinese title

Title: 使用级联累加器高效计算时间指数加权和

Deijany Rodriguez Linares, Oksana Moryakova, Håkan Johansson

Comments: This work has been submitted to the IEEE for possible publication

Subjects: Signal Processing (eess.SP) ; Data Structures and Algorithms (cs.DS) ; Numerical Analysis (math.NA)

[47] arXiv:2509.14807 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: The Complexity of Finding and Counting Subtournaments Show Chinese title

Title: 寻找和计数子竞赛图的复杂性

Simon Döring, Sarah Houdaigoui, Lucas Picasarri-Arrieta, Philip Wellnitz

Subjects: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS)

[48] arXiv:2509.14509 (cross-list from quant-ph) [cn-pdf, pdf, html, other]

Title: Decoded Quantum Interferometry Requires Structure Show Chinese title

Title: 解码量子干涉需要结构

Eric R. Anschuetz, David Gamarnik, Jonathan Z. Lu

Comments: 51 pages, 6 figures

Subjects: Quantum Physics (quant-ph) ; Disordered Systems and Neural Networks (cond-mat.dis-nn) ; Statistical Mechanics (cond-mat.stat-mech) ; Data Structures and Algorithms (cs.DS)