ECCC-Report TR20-075https://eccc.weizmann.ac.il/report/2020/075Comments and Revisions published for TR20-075en-usTue, 19 May 2020 20:37:57 +0300
Revision 1
| Rigid Matrices From Rectangular PCPs |
Amey Bhangale,
Prahladh Harsha,
Orr Paradise,
Avishay Tal
https://eccc.weizmann.ac.il/report/2020/075#revision1We 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 considerably 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 $\delta \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 $\delta N^2$-far (in Hamming distance) from matrices of rank at most $2^{\log N/\Omega(\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.Tue, 19 May 2020 20:37:57 +0300https://eccc.weizmann.ac.il/report/2020/075#revision1
Paper TR20-075
| Rigid Matrices From Rectangular PCPs |
Amey Bhangale,
Prahladh Harsha,
Orr Paradise,
Avishay Tal
https://eccc.weizmann.ac.il/report/2020/075We 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 considerably 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 $\delta \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 $\delta N^2$-far (in Hamming distance) from matrices of rank at most $2^{\log N/\Omega(\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.Wed, 06 May 2020 22:28:27 +0300https://eccc.weizmann.ac.il/report/2020/075