May, 2023

通过动态规划和次线性分割改进 Allen 的区间代数算法

PDF
TL;DR本文提出了一种新颖的动态规划和亚线性分区技术框架来解决 NP-hard 的定性推理问题，将 Allen 的时间区间代数的复杂度从 O（（1.0615n）^ n）降至 O（（cn /log n）^ n）；提出的算法技术不仅大大提高了 NP-hard 定性推理问题的最新技术水平，而且还可能适用于许多需要 $2^（O（n））$ 分辨率的问题。
qualitative reasoningtemporal reasoningdynamic programmingcomputational complexityalgorithmic technique
发现论文，激发创造
  • 一种关于区间数据最佳分割的算法

    本文提出一种搜索数据点划分的算法，可以自动确定模型阶数，适用于高维数据，可解决信号处理中的多种问题。

    Sep, 2003

  • 定性推理问题的多元复杂度分析

    本文介绍了单指数算法，并通过多元分析研究了时间推理问题，特别是针对 Allen 的时间间隔代数，证明了一个新问题可以在单指数时间内解决，并且这种方法可以更广泛地用于其他问题。

    Sep, 2022

  • 快速平衡划分尽管在网格和树上也很困难

    本文探讨了 k-Balanced Partitioning 问题的两类近似算法：快速但准确度不高和保证高质量准确度但速度较慢的算法。研究表明，这种运行时间和解决方案质量之间的权衡是必要的。我们还提出了一种基于图形类别的规约框架，以证明了该问题的困难性。本文是该问题的第一次双层次不可近似结果。

    Nov, 2011

  • 利用流和重新加权特征值进行有向图划分的快速算法

    提供了一种基于对称正定半定规划的指向图划分算法，同时证明了此算法具备较好的扩展性。

    Jun, 2023

  • 部分有序时间一致性检查的快速算法

    本文研究了部分有序时间点代数的网络一致性问题，在构建类似于全序的结构的基础上，通过贪婪策略将其扩展到解决方案，并开发了一种运行时间为 O^*((0.26n)^n) 的算法，比以前快得多。

    May, 2023

  • 神经网络的区间算法基本限制

    本文讨论了区间分析（或区间边界传播，IBP）用于验证和训练可靠机器学习的深度神经网络的可行性问题。研究发现，对于任何深度神经网络分类只有三个点，存在 IBP 无法证明的有效规范。此外，在单隐藏层神经网络的限制情况下，存在一组点，无论采用多少隐藏层，都无法通过区间分析来证明其分类鲁棒性。

    Dec, 2021

  • 图分割、图稀疏化和解线性系统的近线性时间算法

    这篇论文分为三篇，分别为 arXiv:0809.3232, arXiv:0808.4134, arXiv:cs/0607105。

    Oct, 2003

  • 使用优化获得宽度无关、并行、简单、更快的正定半定规划求解器

    本文针对包装和覆盖半正定程序（或正半定规划）的近似求解，研究了多对数深度算法的设计，并提出了一种基于优化框架的简单算法，其正确性基于 Lieb-Thirring 不等式的新矩阵不等式和梯度截断技术的随机变体。

    Jul, 2015

  • 概率多项式和汉明最近邻

    本文提出了一种利用概率多项式计算对数域上任意对称布尔函数并控制误差的低阶多项式方案，借此算法可在超对数维度中在真正的亚二次时间内求解汉明距离，并且能够对内积最大的向量，有最近的 ell1 对和杰卡德系数最大的向量对进行计算。

    Jul, 2015

  • 学习半空间交集的改进难度结果

    通过与半空间和所谓的并行煎饼分布的新颖联系，我们以统一的方式获得了较强（而且令人惊讶地简单）的在不适当的情况下学习半空间交集的下界，这是过去几年强大的高维统计学中许多下界构造的核心，我们还给出了统计查询框架下的无条件难度结果。

    Feb, 2024