Sliding Scale Conjectures in PCP
Dana Moshkovitz · ACM SIGACT News · 2019
The PCP (i.e., Probabilistically Checkable Proofs) Theorem [8, 7, 22, 5, 4] states that any mathematical proof can be converted to a format that can be checked by a veri er making only a constant number of queries to the proof. The veri er picks the queries in a randomized way and might err with low probability.