Jun, 2017

P 问题的近似难度的分布式 PCP 定理

PDF
TL;DR这篇论文提出了一个新的概率可检验证明 (PCP) 的分布式模型，使用该模型，将 Strong Exponential Time Hypothesis (SETH) 归约到 P 问题的近似，尤其是对于 Bichromatic Maximum Inner Product 问题，我们获得了几乎多项式的因子，仅低于 SETH 的约束因子，这是首次实现此类归约。
probabilistically checkable proofsdistributed modelstrong exponential time hypothesisinapproximability factorsbichromatic maximum inner product
发现论文，激发创造
  • PCP Theorems, SETH 和更多：朝着证明亚线性时间 不可近似性的目标迈进

    本文提出了基于 PCP 的定理用于部分线性时间内无法逼近问题，通过从 Set Containment 问题中的 MA 协议进行改编证明了部分线性时间内 PCP 定理并且应用到了已有的和新的无法逼近问题中。这个部分线性时间内的 PCP 定理对于指导部分线性时间逼近算法的研究至关重要。

    Nov, 2020

  • 近似最近邻搜索的难度

    采用代数几何编码，利用分布式 PCP 框架，证明了近二次运行时间下的条件下的近似双色最近点问题（包括 Euclidean，Manhattan，Hamming 或编辑距离），提出了新的硬度结果，其特别适用于多项式预处理时间的近似最近邻搜索问题。

    Mar, 2018

  • 一个新的多层 PCP 以及超图顶点覆盖问题的困难度

    本文利用有偏 Long-Code 分析组合性质中的 s 个 t 交集自组合来证明当 k≥3 且 ε>0 时 E$k$-Vertex-Cover 问题是 NP 难的，且无法使用因子为 (k-1-ε) 近似，同时也说明该问题可以在因子 k 的误差范围内轻松近似。

    Apr, 2003

  • 并行重复的分析方法

    本文提出了一种研究并行重复的游戏操作的分析框架，并证明了投影游戏的 平行重复乘性和良好逼近性特性，利用该框架，我们可以从基本的 PCP 定理开始，给出了 Label-Cover（1，δ）NP - 完全性的简短证 明，并获得了一些新结果，如具有小 soundness 的投影游戏的平行重复上界及其在集合覆盖和标签覆盖的强近似不可近性界限等。

    May, 2013

  • 相变引起的算法障碍

    研究随机 CSP 问题和多项式时间算法无法寻找解决方案的相位转变，并运用一般技术准确地证明 $k$- 着色的相位转变推出所有已知多项式时间算法的失败点。

    Mar, 2008

  • 多项式对数轮次内求解相关聚类问题的三因素近似算法失效

    本文研究了用于相关聚类问题的并行算法，其中每个不同实体的每对实体都标记为相似或不相似，旨在将实体分成簇以最小化与标签的不一致性，提出了首个多项式对数深度并行算法，并使用比 3 更好的逼近比计算 (2.4 +ϵ) 逼近解，可以将其转换为 (m1.5) 时间顺序算法和带有 (m1.5) 总内存的多项式对数轮次亚线性内存计算算法。

    Jul, 2023

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

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

    Jul, 2015

  • 平均情况复杂度与交错量子计算的近似模拟

    使用 IQP 计算加强量子计算难以经典模拟的猜想，研究了推断两个可信度均值情况下的 IQP 计算难度和经典模拟误差大小；一个关于计算随机基态因子函数硬度，另一个探究低阶多项式零点的计算难度，这两个猜想在最坏情况下得以验证。

    Apr, 2015

  • CSP 的次指数近似算法：从密集到几乎稀疏

    本文从大规模消耗能源问题出发，对 mAP 米级别的近似精度提出解决方案，同时研究了深度的语义信息和有限的上下文信息如何影响计算性能。

    Jul, 2015

  • Sum-Product Networks 的最大后验推断的近似复杂度

    探讨了在总和 - 乘积网络中近似最大后验推断的计算复杂性，证明了在高度为 2 和 3 的树状网络中，这一问题都是 NP 难问题，并提出了一种比传统算法更优秀的简单算法。

    Mar, 2017