Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

We initiate the study of the tradeoff between the {\em length} of a

probabilistically checkable proof of proximity (PCPP) and the

maximal {\em soundness} that can be guaranteed by a $3$-query

verifier with oracle access to the proof. Our main observation is

that a verifier limited to querying a short ...
more >>>

Yotam Dikstein, Irit Dinur

Given a family X of subsets of [n] and an ensemble of local functions $\{f_s:s\to\Sigma \;|\; s\in X\}$, an agreement test is a randomized property tester that is supposed to test whether there is some global function $G:[n]\to\Sigma$ such that $f_s=G|_s$ for many sets $s$. For example, the V-test chooses ... more >>>