<p>In the standard definition of a PCP, the verifier reads the entire input <span class="math-container">$x$</span>. Nevertheless, there is a variant of a PCP, called a &quot;PCP of Proximity&quot; (PCPP) or an &quot;assignment tester&quot;, which also reads only a constant number of <span class="math-container">$x$</span>. The price, however, is that a PCPP cannot tell whether <span class="math-container">$x \in L$</span> - it can only tell if <span class="math-container">$x$</span> is close to <span class="math-container">$L$</span> or not (in Hamming distance).</p>
<p>You can find more details in the relevant chapters of the Arora-Barak book or Goldreich's complexity book.</p>

CC BY-SA 4.0
2024-05-05T13:35:04.210Z
but what's the answer to the question of whether you can get away with only reading a constant number of bits from $x$?
mathworker21
CC BY-SA 4.0
2024-05-05T18:06:12.160Z
Here are some lecture notes that came up by a simple searc for PCP of proximity. https://home.ttic.edu/~prahladh/teaching/07autumn/lectures/lec5.pdf.
Chandra Chekuri
CC BY-SA 4.0
2024-05-05T12:05:27.173Z
2024-05-05T12:05:27.173Z
Or Meir
<p>The PCP theorem (very imprecisely!) states that for every <span class="math-container">$x\in L\in NP$</span> there is a polynomial witness <span class="math-container">$w$</span> such that for some random algorithm it is enough to read a constant number of bits of <span class="math-container">$w$</span> to verify <span class="math-container">$x\in L$</span>.<br />
But all the statements of the PCP theorem that I have found say nothing about how much of <span class="math-container">$x$</span> we need to read.<br />
Doesn't it also follow from known proofs that it is also sufficient to read a constant number of bits from <span class="math-container">$x$</span>?</p>
<p>Admittedly, I'm a very lazy reviewer; it's not just that I don't want to read the proof, I don't even want to read the statement!</p>
<p><strong>Update.</strong> Now I see a very simple reason why this cannot be possible. Assume that <span class="math-container">$x\in L$</span> but if we flip any of its bits, then its not. Denote one such input by <span class="math-container">$x'$</span>. Denote the witness for <span class="math-container">$x$</span> by <span class="math-container">$w$</span>. Then <span class="math-container">$(x',w)$</span> will be also accepted unless the flipped bit of <span class="math-container">$x'$</span> is read, but if we only read a constant part of <span class="math-container">$x$</span>, then chances for this are small.</p>

CC BY-SA 4.0
2024-05-05T08:03:09.037Z
in PCP you need to propagate error locally in x if any error exists, so you need entire x not constant fraction of x!
Mohsen Ghorbani
CC BY-SA 4.0
2024-05-05T14:53:34.750Z
@Mohsen I don't really understand your logic. I'm not checking only constantly many bits from $x$, I also check a constant number of bits from $w$.
domotorp
CC BY-SA 4.0
2024-05-07T03:31:27.290Z
it seems that you cannot even do a polynomial time computable encoding of the input into an error correcting code that one would only need to read a const number of bits, iiuc.
Kaveh
<pcp>
PCP without reading the statement
domotorp
# PCP without reading the statement

(Asked by: username_0 on 2024-05-05)

The PCP theorem (very imprecisely!) states that for every $x\in L\in NP$ there is a polynomial witness $w$ such that for some random algorithm it is enough to read a constant number of bits of $w$ to verify $x\in L$.  
But all the statements of the PCP theorem that I have found say nothing about how much of $x$ we need to read.  
Doesn't it also follow from known proofs that it is also sufficient to read a constant number of bits from $x$?

Admittedly, I'm a very lazy reviewer; it's not just that I don't want to read the proof, I don't even want to read the statement!

**Update.** Now I see a very simple reason why this cannot be possible. Assume that $x\in L$ but if we flip any of its bits, then its not. Denote one such input by $x'$. Denote the witness for $x$ by $w$. Then $(x',w)$ will be also accepted unless the flipped bit of $x'$ is read, but if we only read a constant part of $x$, then chances for this are small.

**Tags:** pcp
> **Comments:**
> **username_1**: in PCP you need to propagate error locally in x if any error exists, so you need entire x not constant fraction of x!  
> **username_0**: @Mohsen I don't really understand your logic. I'm not checking only constantly many bits from $x$, I also check a constant number of bits from $w$.  
> **username_2**: it seems that you cannot even do a polynomial time computable encoding of the input into an error correcting code that one would only need to read a const number of bits, iiuc.  

---

## 1 answers

### Answer by username_3 on 2024-05-05. Score: 11 | Accepted answer

In the standard definition of a PCP, the verifier reads the entire input $x$. Nevertheless, there is a variant of a PCP, called a "PCP of Proximity" (PCPP) or an "assignment tester", which also reads only a constant number of $x$. The price, however, is that a PCPP cannot tell whether $x \in L$ - it can only tell if $x$ is close to $L$ or not (in Hamming distance).

You can find more details in the relevant chapters of the Arora-Barak book or Goldreich's complexity book.

> **Comments:**
> **username_4**: but what's the answer to the question of whether you can get away with only reading a constant number of bits from $x$?  
> **username_5**: Here are some lecture notes that came up by a simple searc for PCP of proximity. https://home.ttic.edu/~prahladh/teaching/07autumn/lectures/lec5.pdf.  

---

