Apr, 2015

FAQ：常见问题解答

PDF
TL;DR研究和定义了 Functional Aggregate Query 问题，并提出了 InsideOut 算法解决该问题。算法使用了变量消除和 Grohe 和 Marx 的分数边缘覆盖框架，以及最近的最优关系连接算法的分析。精确描述了何时变量排序与输入 FAQ 表达式中的变量排序是 “语义等效的”，并设计了一种近似算法来找到具有最佳 “分数 FAQ 宽度” 的等效变量排序。结果涵盖了图形模型推断、矩阵运算、关系连接和逻辑等多个领域。
functional aggregate queryinsideout algorithmvariable eliminationgraphical model inferencematrix operations
发现论文，激发创造
  • 使用近似不动点理论分析聚合答案集编程的语义

    该研究在近似不动点理论的观点下重新考虑了选择用于回答集编程（ASP）中聚合的适当形式化问题，介绍了一种等同于基本 ASP 程序的 Gelfond-Lifschitz 规约的 AFT 形式化，并将其扩展到聚合处理。

    Apr, 2021

  • 基于 EFO_k 的 CQA：超越集合操作的知识图谱复杂查询响应

    为了回答知识图谱上的复杂查询，我们提出了一个综合框架，涵盖了存在性一阶查询的组合空间，并构建了一个 dataset 进行评估。我们的结果揭示了查询难度对结果的影响，并强调了现有数据集构建过程中的系统偏见对查询 - 回答方法的适当发展的重要性。

    Jul, 2023

  • 分而治之：约束满足问题的通用方法

    介绍一种用几何模型来解决多约束条件优化问题的方法，并在布尔可满足性问题和球体堆积问题两个基准测试中说明了其有效性和竞争性。

    Dec, 2007

  • 具有传递角色的表达能力描述逻辑中的有限查询回答

    该研究探讨了有限本体中介查询应答的问题，使用 DLs 描述逻辑中的联合，当仅考虑本体的有限模型时，研究 FOMQA 是相关的，本研究显示了 SOIF 的三个适当片段的 FOMQA 具有可决定性，这是基于模型的特定规律，开发了自动机决策程序。

    Aug, 2018

  • 私密发布合取和统计查询障碍

    本研究提出了两个结果，第一个结果说明了在 Kearns' SQ 模型中，对一组统计查询 C 生成错误率较小的所有答案需要的统计查询次数是对偶学习复杂度；第二个结果能高效地解决问题，只要能够通过子模函数描述 C 的答案集。这两个结果对隐私保护数据分析产生了积极的应用，使其得到了重大进展。

    Nov, 2010

  • 概率逻辑编程的升级变量消除

    本文提出 LP$^2$ 算法来解决概率逻辑编程中的查询问题。LP$^2$ 是通过将 Generalized Counting First Order Variable Elimination (GC-FOVE) 转换为 Prolog Factor Language (PFL) 实现的，并增加了两个新的操作符来处理异构因子。结果表明该方法有潜力超过 PITA 和 ProbLog2。

    May, 2014

  • 一阶逻辑双变量片段中的精确采样

    本文研究了最近由 Wang 等人提出的一阶逻辑采样问题 —— 如何在有限域上高效地采样给定一阶句子的模型？我们将他们对于双变量逻辑 FO^2 的普遍量化子片段 UFO^2 的结果扩展到整个 FO^2 片段。具体来说，我们证明了 FO^2 在采样下的域可扩展性，即存在一种能在域大小多项式时间下运行的 FO^2 采样算法。然后，我们进一步表明，即使存在像所有 x 存在 = ky: φ（x，y）和存在 = kx 为所有 y 的数量约束，如 φ（x，y）的量化器公式，我们的方法也可以保持运作。我们的提出的方法是具有建设性的，由此产生的采样算法在各个领域都有潜在的应用，包括在组合结构和统计关系模型的均匀生成方面以及如 Markov 逻辑网络和概率逻辑程序的采样方面。

    Feb, 2023

  • 知识图谱上存在性一阶查询的推理

    这篇论文通过系统检视问题之前的范围并提出一个新的数据集，讨论了同时出现的新挑战，并提出了一种模糊逻辑理论的新搜索算法，以解决新的公式并在现有公式中胜过以前的方法。

    Apr, 2023

  • 通过查询消除的影响下界

    通过查询消除法，我们对 O'Donnell，Saks，Schramm 和 Servedio 的一个结论给出了更简单的证明，该结论显示了一个函数 f 的零误差随机查询复杂度的下界，其最大影响由 f 的任何变量。我们的下界还适用于 f 的双面误差分布式查询复杂度，并且它允许一个直接扩展，用于证明某些函数的更强下界。

    Feb, 2011

  • 判定肯定存在查询的答案计数：一个复杂度分类

    本文研究了有限结构中存在性正公式的答案数量计数问题，并在有界性条件下给出了关于查询类的三分定理，统一和泛化了关于合取查询和合取查询并的复杂性的已知结果。

    Jan, 2016