Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem
该论文提出了一种基于将索引哈希至 Lévy 过程的新颖通用方案，利用 Lévy-Khintchine 表示定理统一了流数据中 -矩估计的多种现有方法，并扩展了可估计函数的范围至多维及异质情形。
💻 Category
cs.DS
87 篇论文
Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces
该论文针对非正曲率度量空间（Hadamard 空间）中缺乏线性结构导致次梯度构造困难的问题，提出了一种基于 Busemann 函数的新型次梯度定义，并据此构建了具有复杂度保证的随机及增量次梯度优化算法，成功应用于 BHV 树空间等场景下的 -均值问题求解。
Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
该论文提出了一种针对带时间窗旅行商问题（TSPTW）的高效精确算法，证明了经典基准实例因结构可被利用而不再具备代表性，无法有效评估算法性能或作为机器学习训练集。
Time warping with Hellinger elasticity
本文针对取值于任意度量空间的时间序列匹配问题，提出了一种基于 Hellinger 核作为拉伸惩罚项的弹性时间规整算法，该算法具有立方级计算复杂度。
bsort: A theoretically efficient non-comparison-based sorting algorithm for integer and floating-point numbers
本文提出了一种名为 bsort 的非比较排序算法，该算法通过统一处理有符号/无符号整数及浮点数，实现了 的时间复杂度和 的辅助空间复杂度，在小字长数据场景下性能可与主流库中的优化混合算法相媲美。
Unit Interval Selection in Random Order Streams
本文针对随机顺序流模型下的单位区间选择问题，提出了一种仅需线性空间且期望近似比达到 0.7401 的单遍流算法，并证明了该性能提升在空间限制下是可能的，同时给出了相应的空间下界。
A PTAS for Weighted Triangle-free 2-Matching
本文针对加权无三角形 2-匹配问题（WTF2M），提出了一种基于简单局部搜索算法及其非平凡分析的 PTAS，从而在多项式时间内实现了任意精度 的近似解，突破了该问题此前仅有 $2/3$ 近似比的局限。
Fast and Optimal Differentially Private Frequent-Substring Mining
该论文提出了一种新的-差分隐私算法，通过引入基于频繁前后缀结构的候选生成策略和基于频率关系的剪枝技术，在保持近最优误差的同时，将频繁子串挖掘的空间和时间复杂度从之前的显著降低至和，从而实现了可扩展的隐私保护子串挖掘。
Better Bounds for the Distributed Experts Problem
本文提出了一种新的分布式专家问题协议，通过优化通信量实现了比先前工作更优的遗憾界。
On the Online Weighted Non-Crossing Matching Problem
本文研究了欧几里得平面上带权重的在线非交叉匹配问题，证明了确定性算法无法获得非平凡竞争比，但随机化算法可实现常数竞争比，并进一步探讨了可撤销机制、共线点情形及最优解的咨询复杂度上界。
A Critical Pair Enumeration Algorithm for String Diagram Rewriting
本文提出了一种针对对称幺正范畴中无 Frobenius 结构的左连通弦图重写系统的算法，通过超图操作枚举所有临界对，并证明了该算法在自动化临界对分析中的正确性与完备性。
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
该论文将低维欧几里得空间中-中值和-均值问题的-近似算法运行时间从$2^{(1/\varepsilon)^{O(d^2)}}n2^{\tilde{O}(1/\varepsilon)^{d-1}}nd-1$的下界，从而确立了近乎紧致的复杂度界限。
Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
本文研究了带有平局和上下限配额的二部图多对多匹配问题，证明了临界松弛稳定匹配总是存在，并提出了一个多项式时间的 -近似算法来求解最大基数的此类匹配。
Optimizing Sparse SYK
本文研究了稀疏 Sachdev-Ye-Kitaev (SYK) 模型的基态优化问题，证明了当稀疏度参数 时，经典高斯态算法与高效量子算法在寻找近似基态能量方面存在可证明的复杂度分离，从而确立了该模型在稀疏化条件下的量子优势鲁棒性。
Privately Estimating Black-Box Statistics
本文提出了一种在统计效率与 oracle 效率之间进行权衡的差分隐私方案，用于估计任意黑盒函数的统计量，并证明了该方案近乎最优。
Exploration Space Theory: Formal Foundations for Prerequisite-Aware Location-Based Recommendation
本文提出了探索空间理论（EST），通过将知识空间理论形式化地移植到基于位置的推荐系统中，利用格论和形式概念分析建立了兴趣点间先决依赖关系的数学基础，并据此构建了具备线性时间复杂度、推荐有效性保证及可解释性等结构优势的探索空间推荐系统（ESRS）。
Multi-Agent Reinforcement Learning with Submodular Reward
该论文首次建立了具有子模奖励（即边际收益递减）的合作多智能体强化学习框架，并提出了在已知和未知动力学下分别具有多项式复杂度近似保证和 遗憾界的高效算法。
A Class of Unrooted Phylogenetic Networks Inspired by the Properties of Rooted Tree-Child Networks
该论文指出识别树子可定向无根网络是 NP 难的，进而提出了-可切割网络这一新类，证明了其具有多项式时间可识别性，且在该类网络上树包含问题是多项式时间可解的。
Complexity Lower Bounds of Small Matrix Multiplication over Finite Fields via Backtracking and Substitution
该论文提出了一种结合代换法与系统回溯搜索的新方法，用于证明有限域上矩阵乘法的双线性复杂度下界，并成功将 上 $3 \times 3$ 矩阵乘法的双线性复杂度下界从 19 提升至 20。
Approximating Tensor Network Contraction with Sketches
该论文提出了首个能够近似任意（包括含环）张量网络收缩的草图方法，并针对无环张量网络设计了一种在时间和空间复杂度上仅随收缩次数多项式增长的改进算法，克服了现有方法仅支持无环网络且复杂度呈指数级增长的局限。