Huffman-Bucket Sketch: A Simple Algorithm for Cardinality Estimation
本文提出了一种名为 Huffman-Bucket Sketch (HBS) 的简单可合并数据结构，它通过将 HyperLogLog 寄存器分桶并利用基于强集中分布的全局霍夫曼码进行编码，在保持常数级更新时间和可合并性的同时，将空间复杂度优化至最优的 比特。
💻 Category
cs.DS
87 篇论文
Simple minimally unsatisfiable subsets of 2-CNFs
本文研究了 2-CNF 公式的最小不可满足子集（MUS），提出了识别 2-MUS 的线性时间算法，证明了寻找特定类型 MUS 的复杂性差异（如包含一个或两个单元子句的 MUS 可在多项式时间内求解，而判断是否存在亏度为 1 的 MUS 是 NP 完全的），并给出了针对含单元子句 MUS 的增量多项式时间算法。
Linear-Scaling Tensor Train Sketching
本文提出了一种名为块稀疏张量链（BSTT）的结构化随机投影方法，通过统一现有的张量链适配算子并实现仅随张量阶数和子空间维度线性扩展的嵌入与注入性质，显著克服了传统方法在张量阶数上的指数级缩放瓶颈，从而为 QB 分解和随机张量链截断提供了准最优误差保证。
Separating Oblivious and Adaptive Differential Privacy under Continual Observation
该论文通过构造一个基于相关向量查询的问题，首次明确证明了在持续观察模型下，针对固定数据流的非自适应差分隐私算法与针对自适应数据流的差分隐私算法之间存在显著差异：前者能在指数级时间步内保持准确，而后者在常数步后便会失效。
Instruction set for the representation of graphs
本文提出了 IsalGraph，一种将任意有限简单图结构编码为九字符指令字符串的紧凑方法，该方法通过贪心算法实现多项式时间编码，具备无无效状态、同构不变性及与图编辑距离强相关等特性，适用于图相似性搜索、图生成及图条件语言建模等任务。
Testing Graph Properties with the Container Method
本文通过将图容器方法扩展应用于属性测试领域，建立了在稠密图模型中测试-团性质和-可着色性的近乎最优样本复杂度上界。
Online Flexible Busy Time Scheduling on Heterogeneous Machines
本文研究了异构机器上的在线繁忙时间调度问题，针对具有统一长度和截止时间的作业，设计了一个竞争比为 8 的算法并证明了竞争比下界为 2，同时将该算法推广至作业长度均为 的通用情形。
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
该论文提出了一种固定参数可解（FPT）算法，不仅解决了判定图能否被少于 条顶点不相交路径覆盖的长期未决问题，还首次证明了在独立数有界的情况下哈密顿路径判定问题是多项式时间可解的，从而推广了经典的 Gallai-Milgram 定理。
-Motif: Parallel Subgraph Isomorphism via Tabular Operations
本文提出了名为-Motif 的 GPU 加速子图同构算法，该算法通过将图数据转化为表格形式并利用数据库连接与过滤等原语实现大规模并行处理，在量子电路编译等应用中展现出比传统算法高达 595 倍的性能提升。
Space-efficient B-tree Implementation for Memory-Constrained Flash Embedded Devices
本文针对内存受限的嵌入式闪存设备，开发并评估了多种 B 树变体，实验表明即使是最小型设备也能实现高效的 B 树索引，且存储特定优化能带来显著的性能提升。
How to Sort in a Refrigerator: Simple Entropy-Sensitive Strictly In-Place Sorting Algorithms
该论文针对内存受限的嵌入式系统（如冰箱），提出了两种基于堆栈的自然归并排序算法，它们仅需常数级额外空间，且运行时间关于输入数组的基于游程的熵达到最优。
Agnostic learning in (almost) optimal time via Gaussian surface area
本文改进了Klivans等人关于高斯表面面积与多项式逼近度之间关系的分析，将高斯分布下概念类的伪多项式逼近度从提升至，从而在统计查询模型中实现了多项式阈值函数伪学习复杂度的（近）最优界。
Forwarding Packets Greedily
本文针对在线数据包转发问题，在每包仅需经过一或两个路由器的特殊情形下，证明了某种贪婪算法的竞争性比为 $2-2^{1-k}4/3$ 通用下界。
Transversal Rank, Conformality and Enumeration
该论文提出了一种利用“前瞻”方法在 时间内识别超图横截秩并枚举最小击中集的新算法，并证明了将运行时间进一步优化至 等价于 -共形超图识别及均匀超图中最大超团/独立集枚举等组合算法领域的重大突破。
Induced Minors and Coarse Tree Decompositions
本文证明了关于排除完全二部图和网格诱导子图之图的树分解猜想的一个弱化版本，即存在一种树分解，其每个包的特定距离独立数具有对数多项式上界。
Graph Generation Methods under Partial Information
该论文提出了一种基于必要充分区间条件的序贯方法，用于生成具有指定度序列的二分、有向及无向图，并据此开发了适用于不同规模问题的枚举与采样算法，显著提升了在大规模实例下的可扩展性。
The Complexity of Distance- Dominating Set Reconfiguration
本文研究了距离-支配集重配置问题，证明了在分裂图中当时该问题属于类（与时的-完全性形成复杂度二分），并给出了树图上的线性时间算法，同时扩展了平面图、二分图和弦图上的-完全性结果。
Weighted Reservoir Sampling With Replacement from Data Streams
本文提出了一种针对数据流的加权有放回随机采样新方法，该方法仅需单次遍历即可在未知数据规模下生成具有代表性的样本，并经过理论证明与实验验证，其性能优于现有最先进方法。
Efficient Computation of Time-Index Powered Weighted Sums Using Cascaded Accumulators
本文提出了一种利用级联累加器高效计算时间索引幂加权和方法，该方法通过仅需次常数乘法消除了对全数据块存储的需求，从而实现了适用于逐样本处理系统的实时高效计算。
On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
本文研究了带有正析取约束的最短路径问题的参数化复杂性，针对解大小和图 H 的结构性质等参数，提出了多项式核化算法并证明了固定参数可解性。