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 $\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.

- Added Remarks 2.10, 5.3 and 8.3.
- Fixed minor typos, made minor changes to phrasing.

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 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.

Expanded the Related Work section.

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 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.