数据结构与算法

最近提交的作者和标题

• 2025年10月31日， 星期五
• 2025年10月30日， 星期四
• 2025年10月29日， 星期三
• 2025年10月28日， 星期二
• 2025年10月27日， 星期一

查看今天的 新的 变化

2025年10月31日， 星期五 (展示 8 之 8 条目 )

[1] arXiv:2510.26264 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 节省空间的k不匹配文本索引 显示英文标题

标题： Space-Efficient k-Mismatch Text Indexes

Tomasz Kociumaka, Jakub Radoszewski

评论： SODA 2026

主题： 数据结构与算法 (cs.DS)

[2] arXiv:2510.25861 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 在线3出租车在一般度量空间上 显示英文标题

标题： Online 3-Taxi on General Metrics

Christian Coester, Tze-Yang Poon

主题： 数据结构与算法 (cs.DS)

[3] arXiv:2510.26717 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 关于纯粹隐私协方差估计 显示英文标题

标题： On Purely Private Covariance Estimation

Tommaso d'Orsi, Gleb Novikov

评论： 同等贡献

主题： 机器学习 (cs.LG) ; 数据结构与算法 (cs.DS)

[4] arXiv:2510.26679 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 通过矩阵相干性的紧致差分私有PCA 显示英文标题

标题： Tight Differentially Private PCA via Matrix Coherence

Tommaso d'Orsi, Gleb Novikov

评论： SODA 2026；同等贡献

主题： 机器学习 (cs.LG) ; 数据结构与算法 (cs.DS)

[5] arXiv:2510.26587 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 张量分解超越唯一性，应用于最小秩问题 显示英文标题

标题： Tensor decomposition beyond uniqueness, with an application to the minrank problem

Pascal Koiran, Rafael Oliveira

主题： 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 数据结构与算法 (cs.DS) ; 环与代数 (math.RA) ; 表示理论 (math.RT)

[6] arXiv:2510.26324 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 通过结合扩散模型与退火朗之万动力学进行后验采样 显示英文标题

标题： Posterior Sampling by Combining Diffusion Models with Annealed Langevin Dynamics

Zhiyang Xun, Shivam Gupta, Eric Price

评论： 神经信息处理系统大会 2025

主题： 机器学习 (cs.LG) ; 人工智能 (cs.AI) ; 数据结构与算法 (cs.DS) ; 统计理论 (math.ST) ; 机器学习 (stat.ML)

[7] arXiv:2510.26056 (交叉列表自 math.CO) [中文pdf, pdf, html, 其他]

标题： 强生日问题的重新审视 显示英文标题

标题： The Strong Birthday Problem Revisited

Chijul B. Tripathy

评论： 7页

主题： 组合数学 (math.CO) ; 离散数学 (cs.DM) ; 数据结构与算法 (cs.DS)

[8] arXiv:2510.25165 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 大多数Juntas饱和硬核引理 显示英文标题

标题： Most Juntas Saturate the Hardcore Lemma

Vinayak M. Kumar

评论： 13页，SOSA 2026

主题： 计算复杂性 (cs.CC)

2025年10月30日， 星期四 (展示 8 之 8 条目 )

[9] arXiv:2510.25664 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： $\{s,t\}$-子模函数的分离主划分序列 显示英文标题

标题： $\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Daniel P. Szabo

主题： 数据结构与算法 (cs.DS)

[10] arXiv:2510.25043 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 边缘图多胞形 显示英文标题

标题： Hedgegraph Polymatroids

Karthekeyan Chandrasekaran, Chandra Chekuri, Weihang Wang, Weihao Zhu

主题： 数据结构与算法 (cs.DS)

[11] arXiv:2510.24954 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 重新激发Thorup的捷径猜想 显示英文标题

标题： Reviving Thorup's Shortcut Conjecture

Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller

主题： 数据结构与算法 (cs.DS)

[12] arXiv:2510.25746 (交叉列表自 cs.CR) [中文pdf, pdf, html, 其他]

标题： 精确的zCDP特性对于基本的差分隐私机制 显示英文标题

标题： Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms

Charlie Harrison, Pasin Manurangsi

主题： 密码学与安全 (cs.CR) ; 数据结构与算法 (cs.DS)

[13] arXiv:2510.25670 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 谱扰动界限用于低秩逼近及其在隐私中的应用 显示英文标题

标题： Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy

Phuc Tran, Nisheeth K. Vishnoi, Van H. Vu

评论： 神经信息处理系统大会 2025

主题： 机器学习 (cs.LG) ; 密码学与安全 (cs.CR) ; 数据结构与算法 (cs.DS) ; 数值分析 (math.NA) ; 谱理论 (math.SP)

[14] arXiv:2510.25571 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 噪声下的低秩逆近似扰动界 显示英文标题

标题： Perturbation Bounds for Low-Rank Inverse Approximations under Noise

Phuc Tran, Nisheeth K. Vishnoi

评论： 神经信息处理系统大会 2025

主题： 机器学习 (cs.LG) ; 数据结构与算法 (cs.DS) ; 数值分析 (math.NA) ; 谱理论 (math.SP) ; 统计理论 (math.ST)

[15] arXiv:2510.25541 (交叉列表自 math.PR) [中文pdf, pdf, html, 其他]

标题： 从$\ell_2$到$\ell_p$的快速降维 显示英文标题

标题： Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$

Rafael Chiclana, Mark Iwen

评论： 17页 0图

主题： 概率 (math.PR) ; 数据结构与算法 (cs.DS)

[16] arXiv:2510.25451 (交叉列表自 cs.DC) [中文pdf, pdf, html, 其他]

标题： 像能吸引像吗？ 网络中同名聚集的研究 显示英文标题

标题： Can Like Attract Like? A Study of Homonymous Gathering in Networks

Stéphane Devismes, Yoann Dieudonné, Arnaud Labourel

主题： 分布式、并行与集群计算 (cs.DC) ; 数据结构与算法 (cs.DS)

2025年10月29日， 星期三 (展示 5 之 5 条目 )

[17] arXiv:2510.24621 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 鲁棒几何中位数的压缩集：消除异常值规模依赖性 显示英文标题

标题： Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers

Ziyi Fang, Lingxiao Huang, Runkai Yang

评论： 这篇论文已被NeurIPS 2025接收

主题： 数据结构与算法 (cs.DS) ; 计算几何 (cs.CG) ; 机器学习 (cs.LG) ; 机器学习 (stat.ML)

[18] arXiv:2510.24098 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 动态复制在分布式数据访问中的竞争力 显示英文标题

标题： On Competitiveness of Dynamic Replication for Distributed Data Access

Tianyu Zuo, Xueyan Tang, Bu Sung Lee, Jianfei Cai

评论： 论文的扩展版本，将发表于ICDCN 2026会议

主题： 数据结构与算法 (cs.DS)

[19] arXiv:2510.23913 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 非均匀顶点测度的扩展分解 显示英文标题

标题： Expander Decomposition for Non-Uniform Vertex Measures

Daniel Agassy, Dani Dorfman, Haim Kaplan

主题： 数据结构与算法 (cs.DS)

[20] arXiv:2510.24068 (交叉列表自 cs.DM) [中文pdf, pdf, html, 其他]

标题： 带有真实周期的Pinwheel调度 显示英文标题

标题： Pinwheel Scheduling with Real Periods

Hiroshi Fujiwara, Kota Miyagi, Katsuhisa Ouchi

主题： 离散数学 (cs.DM) ; 数据结构与算法 (cs.DS)

[21] arXiv:2510.23628 (交叉列表自 physics.soc-ph) [中文pdf, pdf, html, 其他]

标题： 有偏和相关评价下的匹配 显示英文标题

标题： Matchings Under Biased and Correlated Evaluations

Amit Kumar, Nisheeth K. Vishnoi

评论： 将出现在NeurIPS 2025上

主题： 物理与社会 (physics.soc-ph) ; 计算机与社会 (cs.CY) ; 数据结构与算法 (cs.DS) ; 计算机科学与博弈论 (cs.GT) ; 理论经济学 (econ.TH)

2025年10月28日， 星期二 (展示 15 之 15 条目 )

[22] arXiv:2510.22882 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 多路协同排序：有序序列的索引空间划分无需合并 显示英文标题

标题： Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge

Amit Joshi

评论： 4页

主题： 数据结构与算法 (cs.DS)

[23] arXiv:2510.22845 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 在超网格上测试禁止的顺序模式属性 显示英文标题

标题： Testing forbidden order-pattern properties on hypergrids

Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg, Nithin Varma

评论： 51页。7图。将发表于SODA 2026。这是完整版本

主题： 数据结构与算法 (cs.DS)

[24] arXiv:2510.22837 (交叉列表自 cs.DS) [中文pdf, pdf, 其他]

标题： 通过K-脊柱的分层指数搜索 显示英文标题

标题： Hierarchical Exponential Search Via K-Spines

Bob Dong

评论： 这是一次无意中提前上传的正在进行中的协作草案。该帖子发布过早，未经公众发布。

主题： 数据结构与算法 (cs.DS)

[25] arXiv:2510.22816 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： $L_p$在分布式数据流中的采样及其在对抗鲁棒性中的应用 显示英文标题

标题： $L_p$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness

Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou

评论： SODA 2026

主题： 数据结构与算法 (cs.DS)

[26] arXiv:2510.22721 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 更快的负权最短路径和有向低直径分解 显示英文标题

标题： Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions

Jason Li, Connor Mowry, Satish Rao

评论： 未发表的预印本2411.19449和2505.10244的合并。已被SODA 2026接收

主题： 数据结构与算法 (cs.DS)

[27] arXiv:2510.22662 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 生成完全图的生成树的枢轴格雷码在常数摊销时间内 显示英文标题

标题： Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time

Bowie Liu, Dennis Wong, Chan-Tong Lam, Sio-Kei Im

评论： 被SODA 2026接收

主题： 数据结构与算法 (cs.DS) ; 离散数学 (cs.DM)

[28] arXiv:2510.22490 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 高维中的树嵌入：动态和大规模并行 显示英文标题

标题： Tree Embedding in High Dimensions: Dynamic and Massively Parallel

Gramoz Goranci, Shaofeng H.-C. Jiang, Peter Kiss, Qihao Kong, Yi Qian, Eva Szilagyi

主题： 数据结构与算法 (cs.DS)

[29] arXiv:2510.22430 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 关于看起来像路径的整数规划 显示英文标题

标题： On Integer Programs That Look Like Paths

Marcin Briański, Alexandra Lassota, Kristýna Pekárková, Michał Pilipczuk, Janina Reuter

主题： 数据结构与算法 (cs.DS)

[30] arXiv:2510.22401 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： Johnson-Lindenstrauss 引理超越欧几里得几何 显示英文标题

标题： Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry

Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, Cheng Xin

评论： 被Neurips 2025接收

主题： 数据结构与算法 (cs.DS)

[31] arXiv:2510.22193 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： （近似）通过卷积的矩阵乘法 显示英文标题

标题： (Approximate) Matrix Multiplication via Convolutions

Kevin Pratt, Yahel Uffenheimer, Omri Weinstein

主题： 数据结构与算法 (cs.DS) ; 离散数学 (cs.DM)

[32] arXiv:2510.22060 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 离散点巡逻的最优密度界限 显示英文标题

标题： An Optimal Density Bound for Discretized Point Patrolling

Ahan Mishra

评论： SODA 2026

主题： 数据结构与算法 (cs.DS)

[33] arXiv:2510.23438 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 随机噪声下的聚类共轭集 显示英文标题

标题： Coresets for Clustering Under Stochastic Noise

Lingxiao Huang, Zhize Li, Nisheeth K. Vishnoi, Runkai Yang, Haoyu Zhao

评论： 这篇论文已被NeurIPS 2025接受

主题： 机器学习 (cs.LG) ; 计算几何 (cs.CG) ; 数据结构与算法 (cs.DS) ; 机器学习 (stat.ML)

[34] arXiv:2510.23039 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 近似最近邻和核密度估计的次线性草图 显示英文标题

标题： Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation

Ved Danait, Srijan Das, Sujoy Bhore

评论： 28页，11图

主题： 机器学习 (cs.LG) ; 数据结构与算法 (cs.DS) ; 机器学习 (stat.ML)

[35] arXiv:2510.22088 (交叉列表自 math.OC) [中文pdf, pdf, html, 其他]

标题： 带有Lewis权重的准自协调优化 显示英文标题

标题： Quasi-Self-Concordant Optimization with Lewis Weights

Alina Ene, Ta Duy Nguyen, Adrian Vladu

主题： 优化与控制 (math.OC) ; 数据结构与算法 (cs.DS)

[36] arXiv:2510.22040 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 广义的Top-k Mallows模型用于排序选择 显示英文标题

标题： Generalized Top-k Mallows Model for Ranked Choices

Shahrzad Haddadan, Sara Ahmadian

主题： 机器学习 (cs.LG) ; 数据结构与算法 (cs.DS) ; 机器学习 (stat.ML)

2025年10月27日， 星期一 (展示 11 之 11 条目 )

[37] arXiv:2510.21700 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： O(1) distortion 平面模拟器用于字符串图 显示英文标题

标题： O(1)-Distortion Planar Emulators for String Graphs

Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, Da Wei Zheng

主题： 数据结构与算法 (cs.DS) ; 计算几何 (cs.CG) ; 离散数学 (cs.DM) ; 组合数学 (math.CO) ; 度量几何 (math.MG)

[38] arXiv:2510.21613 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 超越平滑分析：通过书籍分析单纯形法 显示英文标题

标题： Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book

Eleon Bach, Alexander E. Black, Sophie Huiberts, Sean Kafer

评论： 42页

主题： 数据结构与算法 (cs.DS) ; 优化与控制 (math.OC)

[39] arXiv:2510.21540 (交叉列表自 cs.DS) [中文pdf, pdf, 其他]

标题： 在稀疏图中，将绿色桥梁最优放置于近距离栖息地 显示英文标题

标题： Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs

Christian Wallisch, Till Fluschnik, Leon Kellerhals

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC)

[40] arXiv:2510.21423 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 模糊描述逻辑在Gödel语义下的解释近似最小化 显示英文标题

标题： Approximate minimization of interpretations in fuzzy description logics under the Gödel semantics

Linh Anh Nguyen

主题： 数据结构与算法 (cs.DS)

[41] arXiv:2510.21327 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 关于分布式边着色和定向问题的复杂性 显示英文标题

标题： On the Complexity of Distributed Edge Coloring and Orientation Problems

Sebastian Brandt, Fabian Kuhn, Zahra Parsaeian

主题： 数据结构与算法 (cs.DS)

[42] arXiv:2510.21287 (交叉列表自 cs.DS) [中文pdf, pdf, 其他]

标题： 不可拆分的代价流从无权重误差有界变体 显示英文标题

标题： Unsplittable Cost Flows from Unweighted Error-Bounded Variants

Chaitanya Swamy, Vera Traub, Laura Vargas Koch, Rico Zenklusen

主题： 数据结构与算法 (cs.DS) ; 离散数学 (cs.DM)

[43] arXiv:2510.21128 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 一种在噪声下的子模最大化统一方法 显示英文标题

标题： A Unified Approach to Submodular Maximization Under Noise

Kshipra Bhawalkar, Yang Cai, Zhe Feng, Christopher Liaw, Tao Lin

评论： 被NeurIPS 2025接受

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 机器学习 (cs.LG)

[44] arXiv:2510.21058 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 最短路径向量成本的近似难度 显示英文标题

标题： Hardness of Approximation for Shortest Path with Vector Costs

Charlie Carlson, Yury Makarychev, Ron Mosenzon

评论： 33页，1图，将发表于SODA 2026

主题： 数据结构与算法 (cs.DS)

[45] arXiv:2510.21589 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 相对误差单调性测试 显示英文标题

标题： Relative-error unateness testing

Xi Chen, Diptaksho Palit, Kabir Peshawaria, William Pires, Rocco A. Servedio, Yiding Zhang

主题： 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 数据结构与算法 (cs.DS)

[46] arXiv:2510.21414 (交叉列表自 cs.IT) [中文pdf, pdf, html, 其他]

标题： 通用最大似然（列表）解码通过快速向量-矩阵乘法 显示英文标题

标题： Universal Maximum Likelihood (List) Decoding via Fast Vector-Matrix Multiplication

Hoang Ly, Emina Soljanin

主题： 信息论 (cs.IT) ; 数据结构与算法 (cs.DS)

[47] arXiv:2510.21055 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 在线多类选择的群体公平性保证 显示英文标题

标题： Online Multi-Class Selection with Group Fairness Guarantee

Faraz Zargari, Hossein Nekouyan, Lyndon Hallett, Bo Sun, Xiaoqi Tan

主题： 机器学习 (cs.LG) ; 数据结构与算法 (cs.DS)