论文标题
矩形PCP的刚性矩阵
Rigid Matrices From Rectangular PCPs
论文作者
论文摘要
我们介绍了一种PCP的变体，我们称为矩形PCP，其中证明被认为是方形矩阵，而验证者使用的随机硬币可以分为两个不相交组，一个确定每个查询的行，而另一个确定列的行。 我们构建了高效，短，光滑且（几乎）矩形的PCP。作为关键应用程序，我们表明，当将$ ntime（2^n）$中的硬语言证明（当被视为矩阵时）经常是僵硬的。这加强并简化了Alman和Chen [Focs，2019]的最新结果，该结果在FNP中构建了明确的刚性矩阵。也就是说，我们证明了以下定理： - 有一个常数$δ\ in（0,1）$，因此有一个FNP机机，对于无限的多个$ n $，输入$ 1^n $ outputs $ n \ times $ n \ times n $ n $矩阵中的条目中的条目中的$ \ mathbb {f} _2 $ the $Δn^$ -Far $ 2 $ -far（in Matriring）at hamming deck at hamming farge， n/ω（\ log \ log n）} $。 我们的矩形PCP的构建始于分析Ben-Sasson，Goldreich，Harsha，Sudan和Vadhan的芦苇基于芦苇的外部PCP的查询[Sicomp，2006年； 2006; CCC，2005年]。然后，我们展示如何在PCP组成和平滑度诱导转换下保留矩形。这种保证权证完善了矩形的概念，我们为外部PCP及其转换证明了这一点。
We introduce a variant of PCPs, that we refer to as rectangular PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the row of each query and the other determining the column. We construct PCPs that are efficient, short, smooth and (almost-)rectangular. As a key application, we show that proofs for hard languages in $NTIME(2^n)$, when viewed as matrices, are rigid infinitely often. This strengthens and simplifies a recent result of Alman and Chen [FOCS, 2019] constructing explicit rigid matrices in FNP. Namely, we prove the following theorem: - There is a constant $δ\in (0,1)$ such that there is an FNP-machine that, for infinitely many $N$, on input $1^N$ outputs $N \times N$ matrices with entries in $\mathbb{F}_2$ that are $δN^2$-far (in Hamming distance) from matrices of rank at most $2^{\log N/Ω(\log \log N)}$. Our construction of rectangular PCPs starts with an analysis of how randomness yields queries in the Reed--Muller-based outer PCP of Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan [SICOMP, 2006; CCC, 2005]. We then show how to preserve rectangularity under PCP composition and a smoothness-inducing transformation. This warrants refined and stronger notions of rectangularity, which we prove for the outer PCP and its transforms.
