论文标题
PCP定理，Seth等：旨在证明亚线性时间不易Xibibibibibibility
PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability
论文作者
论文摘要
在本文中，我们提出了类似pcp的定理，以实现亚线性时间的不易Xibibibibibility。 Abboud等。已经设计了分布式的PCP框架，以实现次级时间不Xibibibibibibibibibility。我们表明，可以将分布式PCP定理概括为证明任意多项式时间的不易Ximibibibibility，但在线性情况下失败。我们通过从MA协议中适应集合遏制问题来证明次线性PCP定理，并展示如何使用定理证明现有和新的不耐Xibibibibibility结果，并表现出亚线性PCP定理的功能。考虑到有关亚线性时间算法的新兴研究作品，该子线性PCP定理对于指导研究以下时间近似近似算法很重要。
In this paper we propose the PCP-like theorem for sub-linear time inapproximability. Abboud et al. have devised the distributed PCP framework for sub-quadratic time inapproximability. We show that the distributed PCP theorem can be generalized for proving arbitrary polynomial time inapproximability, but fails in the linear case. We prove the sub-linear PCP theorem by adapting from an MA-protocol for the Set Containment problem, and show how to use the theorem to prove both existing and new inapproximability results, exhibiting the power of the sub-linear PCP theorem. Considering the emerging research works on sub-linear time algorithms, the sub-linear PCP theorem is important in guiding the research in sub-linear time approximation algorithms.
