Doubly Sub-Linear Interactive Proofs of Proximity

An interesting feature of our IPP is that the honest prover strategy is reduced to tolerant testing (or distance approximation) for a property that can be decided by an ROOBP of (at most) the same width and length. A tolerant tester [17] for a property $\mathrm{\Pi }$ gets proximity parameters and is supposed to accept (w.h.p.) if the input is ${\epsilon }_c$-close to the property, and to reject (w.h.p.) if the input is ${\epsilon }_f$-far from the property. The complexity is usually measured as a function of the gap ${\epsilon }_f-{\epsilon }_c$ (and possibly also of the input length).

Theorem 1 follows by plugging any tolerant tester for constant-width ROOBPs into our general reduction (which is stated in Theorem 2). While, as noted above, Newman’s tester for ROOBPs[16] is not tolerant, we show that that it can be made tolerant. This contribution of the current work is presented in the full version of the article.

Our reduction of the prover’s strategy to tolerant testing ROOBPs actually gives a tolerant dsIPP of ROOBPs, where Tolerant IPPs are defined analogously to tolerant testers.⁵⁵5Specifically, if the input is ${\epsilon }_c$-close to the property, then the honest prover should convince the verifier to accept (w.h.p.); but if the input is ${\epsilon }_f$-far from the property, then the verifier should reject (w.h.p.) regardless of the prover’s strategy. We stress that, while in the context of testing, tolerant testing and distance approximation are equivalent (under suitable parameters), this is not the case for dsIPPs (see Section 2 and Remark 8). Fixing the ROOBP under consideration, the reduction assumes that the honest prover has access to a distance approximator that gets an ROOBP of (at most) the specified width and length, and approximates the distance of an input from the corresponding property (i.e., the property decided by the ROOBP). We need the deviation of the distance approximation to be $O(({\epsilon }_f-{\epsilon }_c)/r)$, and its error probability to be sufficiently small. The approximator only needs to operate on “sub-ROOBPs” of the original ROOBP.

Before stating the reduction, we also specify the access the verifier and the prover need to the ROOBP in order to get sublinear runtimes. We assume that the prover and the verifier have (unit cost) access to two procedures that specify the structure of the ROOBP as follows. The first procedure, given two nodes $u$ and $v$ in the ROOBP, returns a bit indicating whether there is a path from $u$ to $v$. The second procedure gets as input the index $i$ of a layer and returns the vertices in that layer. (We emphasize that these procedures do not depend on the input to the ROOBP: they ignore edge labels and refer to the ROOBP as a directed graph.)

See Theorem 19 for a full and formal statement. As discussed above, Theorem 1 is obtained from the above reduction by plugging in a distance approximator for constant-width ROOBPs, which we construct based on Newman’s (non-tolerant) property tester. While the reduction of Theorem 2 only has polynomial dependence on the width of the ROOBP, Newman’s tester and our tolerant version of it have an exponential dependence on the width of the ROOBP (which is the reason that Theorem 1 holds only for constant width).⁶⁶6In contrast, Theorem 2 holds also for varying width, but in that case the complexities have a multiplicative factor of $\text{poly}(w)$. See the details in Section 4.6.

The straightforward tester for PERM consists of selecting $q=O(\sqrt{n/\epsilon })$ random points in $[n]$, querying the function $f:[n]\to [n]$ on them, and rejecting if and only if collisions are found (among the $f$-images).

Evidently, any $f\in \text{PERM}$ is accepted with probability 1, whereas (as can be seen later) any $f$ that is $\epsilon$-far from PERM is rejected with high constant probability. A similar analysis for the soundness case implies that for any $f$ that is $\epsilon$-far from PERM, if we select $O{(n/\epsilon )}^{0.5+\alpha })$ random points, then we expect to see $\mathrm{\Omega }(n^{2\alpha })$ collisions and that these collisions involve $\mathrm{\Omega }(n^{2\alpha })$ disjoint pairs of points. This leads us to the following protocol.

1. 1.

   The verifier selects $p=O{(n/\epsilon )}^{0.5+\alpha }$ (distinct) random points in $[n]$, denoted $s_1,\mathrm{\dots },s_p$, and sends them to the prover,

2. 2.

   The prover queries the input $f:[n]\to [n]$ on these $p$ sample points, and sends the answers $(a_1,\mathrm{\dots },a_p)\leftarrow (f(s_1),\mathrm{\dots },f(s_p))$ to the verifier.

3. 3.

   The verifier rejects if it sees a collision (i.e., if $a_i=a_j$ for some $i\ne j$).

4. 4.

   Otherwise, it sub-samples $m=O{(n/\epsilon )}^{0.5-\alpha }$ of the original points, queries $f$ on each of these $m$ samples, and accept if and only if all answers match the prover’s answers (i.e., if $f(s_i)=a_i$ for the $i$’s it sub-sampled).

Clearly, $f\in \text{PERM}$ is always accepted. Turning to the soundness analysis, we fix an arbitrary function $f$ that is $\epsilon$-far from PERM and let $C\stackrel{\mathrm{def}}{=}\{x\in [n]:|f^{-1}(f(x))|>1\}$ denote the set of points that form collisions under $f$. Then, $|C|>\epsilon \cdot n$; actually, $|C|-|f(C)|>\epsilon \cdot n$, because modifying $f$ to a permutation requires changing its value on all but a single point in $f^{-1}(y)$ for every $y\in f(C)$.

An analogous consideration applies to the sample of $p$ points, denoted $S=\{s_1,\mathrm{\dots },s_p\}$, that is sent to the prover. Specifically, the answers provided by the prover must disagree with the values of $f$ on at least $|S|-|f(S)|$ points, because for each $s\in S$ the prover must provide different answers to all the other points in $S$ that are in $f^{-1}(f(s))$ (since otherwise the verifier rejects in Step 2). Towards upper-bounding $|f(S)|$, we observe that it is upper-bounded by $|f^{\prime }(S)|$, where $f^{\prime }:[n]\to [n]$ is defined such that for every $x,x^{\prime }\in [n]$ it holds that (i) $f^{\prime }(x)\ne f^{\prime }(x^{\prime })$ whenever $f(x)\ne f(x^{\prime })$ and (ii) for each $x$ that forms a collision under $f$, the restriction of $f^{\prime }$ to $f^{-1}(f(x))$ is 2-to-1 except on at most one element (in case $|f^{-1}(f(x))|$ is odd). Now, we lower-bound $|S|-|f^{\prime }(S)|$ by the number of collisions of $S$ under $f^{\prime }$ (i.e., $|\{\{i,j\}\in \left(\genfrac{}{}{0.0pt}{}{[p]}{2}\right):f^{\prime }(s_i)=f^{\prime }(s_j)\}|$)

First note that the number of collisions of $[n]$ under $f^{\prime }$ is at least ${\sum }_{y\in f(C)}\lfloor |f^{-1}(y)|/2\rfloor$, which is at least $|C|/3>\epsilon n/3$. Hence, with high probability over the choice of $S\in \left(\genfrac{}{}{0.0pt}{}{[n]}{p}\right)$, we get $\mathrm{\Omega }(\epsilon \cdot p^2/n)=\mathrm{\Omega }({(n/\epsilon )}^{2\alpha })$ collisions of $S$ under $f^{\prime }$. In this case, there are $\mathrm{\Omega }({(n/\epsilon )}^{2\alpha })$ disjoint pairs of points in $S$ such that the elements in each pair have the same $f^{\prime }$-image (and hence also the same $f$-image).

Wishing to avoid rejection in Step 2, the prover must cheat on the values of the $\mathrm{\Omega }({(n/\epsilon )}^{2\alpha })$ foregoing points (in $S$), but (with high probability) at least one of these points will appear in the sub-sample that the verifier selects in Step 4 (since the sub-sample rate is $m/p=O{(\epsilon /n)}^{2\alpha }$). Hence, in Step 4, when quering the function $f$ on this sub-sample, the verifier detects this cheating and rejects (w.h.p.). This completes the proof of Theorem 4.

Goldreich and Ron [9] showed a $\mathrm{\Omega }(\sqrt{n})$ lower bound on the query complexity of testing bipartiteness.⁸⁸8Their lower bound, which is stated for general 3-regular graphs, also holds under the additional promise that the graphs are rapidly-mixing (see the exposition in [4, Sec. 9.3.1]). In particular, the distribution of NO cases is concentrated on expander graphs (see [4, Clm. 9.18.1]). A similar analysis shows that the YES cases are bipartite expanders (w.h.p.) A later work of the same authors[8] shows a tester with $\tilde{O}(\sqrt{n})\cdot \text{poly}(1/\epsilon )$ query complexity. We remark that their tester works for general graphs, without needing the rapidly-mixing condition. Rothblum, Vadhan and Wigderson [21] constructed an IPP for an intermediate relaxation of bipartiteness, where the YES case includes all the bipartite graphs, but the NO case includes only the graphs that are both far from bipartite and rapidly-mixing. In their IPP, the verifier’s query complexity is $O(\log (n)/\epsilon )$, but the honest prover is not sub-linear: it has to read the entire graph. Our proof of Theorem 5 uses the [21] protocol, but shows a sublinear-time implementation for the honest prover, where the implementation works for graphs that are both rapidly-mixing and bipartite.

We first recall the[21] protocol. In the basic test, the verifier picks a random vertex $s$, and performs a lazy random walk of length $\mathrm{\ell }=O(\log (n))$, which is long enough to guarantee the “rapidly-mixing” condition (see above), reaching a vertex $t$. The verifier sends $s$ and $t$ to the prover, asks the prover to recover the parity of a (simple) path that leads from $s$ to $t$, and accepts if and only if the answer equals the parity of the number of “real moves” in the lazy walk (i.e., moves in which the walk did not stay in the current vertex). If the graph is bipartite, then the prover, who can read the entire graph, can always answer correctly by checking whether $s$ and $t$ are on the same side of the bipartition. As shown in[21], if the graph is rapidly mixing and $\epsilon$-far from bipartite, then a cheating prover will fail with probability $\mathrm{\Omega }(\epsilon )$. In order to reduce the soundness error (from $1-\mathrm{\Omega }(\epsilon )$ to $1/3$), this basic test is repeated $r=O(1/\epsilon )$ times in parallel (and the verifier accepts if and only if it accepted in all invocations of the basic test).

We construct a sub-linear time honest prover for the basic test. Upon receiving the vertices $s$ and $t$, the prover performs $w=O(\sqrt{n}\cdot \log (1/\epsilon ))$ independent random walks of length $\mathrm{\ell }$ starting at $s$, as well as $w$ independent random walks of length $\mathrm{\ell }$ starting at $t$. Let $W_s$ (resp., $W_t$) denote the set of vertices traversed in (the union of all) the walks that started at $s$ (resp., $t$). The prover checks if there is a vertex $v$ in the intersection of $W_s$ and $W_t$ (i.e., a vertex encounted in a walk that started at $s$ as well as in a walk that started at $t$). If so, then the prover has found a walk from $s$ to $t$ (going through $v$), and it replies with the parity of the number of real moves on this walk.

Soundness follows directly from the soundness of the [21] protocol (since we did not change the verifier). We now argue for completeness (alas not perfect completeness). If the graph is bipartite, then all paths from $s$ to $t$ have the same parity. Thus, whenever the prover finds a path from $s$ to $t$ (i.e., when the intersection is non-empty), then it returns the correct parity. It remains to show that in each of execution of the basic test (i.e., for each $s$ and $t$ sent by the verifier), the intersection of $W_s$ and $W_t$ is non-empty with probability at least $1-(1/3r)$. We show this in Claim 6, which is where we use the condition that the graph is rapidly-mixing, and it follows that the verifier accepts in all $r$ repetitions with probability at least $2/3$.

We focus on the sets $W_s^{\prime }\subset W_s$ and $W_t^{\prime }\subset W_t$ of terminal vertices reached by the random walks (i.e., the final vertex in each walk), and show that these subsets intersect with probability at least $1-(1/3r)$. Using the rapidly-mixing condition, observe first that taking $w=O(\sqrt{n}\cdot \log (1/\epsilon ))=O(\sqrt{n}\log r)$ independent walks from $s$, with probability at least $1-(1/6r)$, the number of distinct vertices reached (i.e., the size of the set $W_s^{\prime }$) is $\mathrm{\Omega }(\sqrt{n})$. Assuming that this event occurs, and recalling that each of the random walks starting at $t$ is rapidly-mixing, we infer that, with probability at least $\mathrm{\Omega }(1/\sqrt{n})$, such a walk terminates in a vertex that resides in $W_s^{\prime }$. Recalling that there are $O(\sqrt{n}\cdot \log r)$ walks starting at $t$, the probability that they all land outside of $W_s^{\prime }$ is thus at most $1/6r$. The claim follows. $\mathrm{⊲}$

Assume $\text{wt}(x)=\sigma$ and $V$ interacts with $P$. We observe that at any recursion level (but the base level), the following claim holds: If our input is $x^{\prime }$ and our weight parameter is ${\sigma }^{\prime }$ such that $|\text{wt}(x^{\prime })-{\sigma }^{\prime }|\le \frac{\delta |x^{\prime }|}{2}$, then with probability at least $1-\eta \cdot k$, the prover $P$ sends $({\sigma }_1^{\prime },\mathrm{\dots },{\sigma }_k^{\prime }$) to $V$ such that the following holds:

1. 1.

   The verifier doesn’t reject in Step $4(a)$ (i.e., $|{\sigma }^{\prime }-{\sum }_i{\sigma }_i^{\prime }|\le \delta |x^{\prime }|$).

2. 2.

   The protocol is recursively invoked with some $x_i^{\prime }$ and ${\sigma }_i^{\prime }$ for which $|\text{wt}(x_i^{\prime })-{\sigma }_i^{\prime }|\le \frac{\delta |x^{\prime }|}{2}$.

The claims follows from the fact that $P$ runs the approximator on every $x_i^{\prime }$ with deviation parameter $\frac{\delta }{2}$ and error probability parameter $\eta$. Then, since we start with $\text{wt}(x)=\sigma$, with probability at least $1-\eta \cdot k\cdot r_0$, the verifier doesn’t reject in Step $4(a)$ in all the $r_0$ recursion levels. By the second item of the claim, the base of the recursion is also invoked with an input $x^{\prime }$ and weight parameter is ${\sigma }^{\prime }$ such that $|\text{wt}(x^{\prime })-{\sigma }^{\prime }|\le \frac{\delta |x^{\prime }|}{2}$, and the verifier accepts. Since we repeat the protocol for $O(\frac{1}{\epsilon })$ times, we get that the verifier accepts in all invocations with probability at least $1-t\cdot \eta$ where $t=O(\frac{k\cdot r_0}{\epsilon })$. Then, since we set $\eta =0.01\cdot \frac{1}{t}=O(\frac{\epsilon }{k\cdot r_0})$, we get that $V$ accepts with high constant probability in all invocations.

Assume $|\text{wt}(x)-\sigma |>\epsilon n$. We observe that in each recursion level, we lose at most an additive factor of $\delta$. Since we set $\delta =\frac{\epsilon }{3r_0}$, we get that after $r_0$ rounds, we are still at distance at least $\frac{\epsilon }{2}$ from a valid assertion. Thus, the verifier rejects with probability at least $\mathrm{\Omega }(\epsilon )$ in each invocation, and therefore rejects with high constant probability in at least one of the $O(\frac{1}{\epsilon })$ invocations.