(Lemma 11), we can estimate this quantity using a number of queries that
depends on $\widetilde{W}_{-}(P_{G_{\phi}})$. By Lemma 42, we have that
$\widetilde{W}_{-}(P_{G_{\phi}})\leq 2l^{0pt_{\vee}},$ so we can estimate
$w_{+}(x)=R_{s,t}(G_{\phi}(x))$ in
$\textstyle\widetilde{O}\left(\frac{1}{\varepsilon^{2/3}}\sqrt{w_{+}(x)}\widetilde{W}_{-}^{1/2}\right)=\widetilde{O}\left(\frac{1}{\varepsilon^{2/3}}\sqrt{R_{s,t}(G_{\phi}(x))l^{0pt_{\vee}}}\right)$
queries. Similarly, $R_{s,t}(G^{\prime}_{\phi}(x))={2}w_{-}(x,P_{G_{\phi}})$
for all 0-instances, and $\widetilde{W}_{+}\leq\frac{1}{2}l^{0pt_{\wedge}}$,
so we can estimate $R_{s,t}(G^{\prime}_{\phi}(x))$ in
$\widetilde{O}\left(\frac{1}{\varepsilon^{2/3}}\sqrt{R_{s,t}(G_{\phi}^{\prime}(x))l^{0pt_{\wedge}}}\right)$
queries. ∎

To prove Lemma 42, we will use the following observation, which gives an upper
bound on the length of the longest self-avoiding $st$-path in $G_{\phi}$, in
terms of the $\wedge$-depth of $\phi$. This bound is not tight in general.

######  Claim 43.

Let $\phi$ be an and-or formula with constant fan-in $l$. If $\phi$ has
$\wedge$-depth $0pt_{\wedge}$, then the longest self-avoiding path connecting
$s$ and $t$ in $G_{\phi}$ has length at most $l^{0pt_{\wedge}}$.

###### Proof.

We will prove the statement by induction. If $\phi$ has $\wedge$-depth
$0pt_{\wedge}=0$, then it has no $\wedge$-nodes. Thus, it is easy to see that
$G_{\phi}$ has only two vertices, $s$ and $t$, with some number of edges
connecting them, so every $st$-path has length 1.

Suppose $\phi$ has $\wedge$-depth $0pt_{\wedge}>0$. First, suppose
$\phi=\phi_{1}\wedge\dots\wedge\phi_{l}$. Then since $G_{\phi}$ consists of
$G_{\phi_{1}},\dots,G_{\phi_{l}}$ connected in series, any $st$-path in
$G_{\phi}$ consists of an $st$-path in $G_{\phi_{1}}$, followed by an
$st$-path in $G_{\phi_{2}}$, etc. up to an $st$-path in $G_{\phi_{l}}$, so if
$0pt_{\wedge}(\phi_{i})$ is the $\wedge$-depth of $\phi_{i}$, then the longest
$st$-path in $G_{\phi}$ has length at most:

$\displaystyle l^{0pt_{\wedge}(\phi_{1})}+\dots+l^{0pt_{\wedge}(\phi_{l})}\leq
ll^{0pt_{\wedge}-1}=l^{0pt_{\wedge}}.$ (86)

If $\phi=\phi_{1}\vee\dots\vee\phi_{l}$, then
$\max_{i}0pt_{\wedge}(\phi_{i})=0pt_{\wedge}(\phi)=0pt_{\wedge}$, and
$G_{\phi}$ consists of $G_{\phi_{1}},\dots,G_{\phi_{l}}$, connected in
parallel. Any self-avoiding $st$-path must include exactly one edge adjacent
to $s$ and one edge adjacent to $t$. However, any path that includes an edge
from $G_{\phi_{i}}$ and $G_{\phi_{j}}$ for $i\neq j$ must go through $s$ or
$t$, so it must have more than one edge adjacent to $s$, or more than one edge
adjacent to $t$, so such a path can never be a self-avoiding $st$-path. Thus,
any self-avoiding $st$-path must be contained completely in one of the
$G_{\phi_{i}}$. The longest such path is thus the longest self-avoiding
$st$-path in any of the $G_{\phi_{i}}$, which, by induction, is
$\max_{i}l^{0pt_{\wedge}({\phi_{i}})}=l^{0pt_{\wedge}}$. ∎

Now we can prove Lemma 42:

###### Proof of Lemma 42.

To begin, we will prove the upper bound on $\widetilde{W}_{+}$. Suppose
$|\tilde{w}\rangle$ is an optimal approximate positive witness for $x$. By
Claim 30, if $|\tilde{w}\rangle$ is an approximate positive witness, then
since $A|\tilde{w}\rangle=\tau$, and $c$ has unit value on all edges of $G$,
$\theta(u,v,\lambda)=\langle{u,v,\lambda}|{\tilde{w}}\rangle-\langle{v,u,\lambda}|{\tilde{w}}\rangle$
is a unit flow on $G$. Since $|\tilde{w}\rangle$ is an approximate positive
witness for $x$, it has minimal error for $x$, so it minimizes
$\left\|\Pi_{H(x)^{\bot}}|\tilde{w}\rangle\right\|^{2}$, and since it is
optimal, it minimizes $\left\||\tilde{w}\rangle\right\|^{2}$ over all
approximate positive witnesses. Define
$|\theta\rangle=\sum_{(u,v,\lambda)\in\overrightarrow{E}(G)}\theta(u,v,\lambda)|u,v,\lambda\rangle$,
so we know that $\frac{1}{2}|\theta\rangle$ also maps to $\tau$ under $A$, so
is also a positive witness in $P_{G_{\phi}}$.Then we have

$\left\|\Pi_{H(x)^{\bot}}|\theta\rangle\right\|^{2}=2\\!\\!\\!\\!\sum_{\begin{subarray}{c}(u,v,\lambda)\in\\\
\overrightarrow{E}(G)\setminus\overrightarrow{E}(G(x))\end{subarray}}\\!\\!\\!\\!\langle{u,v,\lambda}|{\tilde{w}}\rangle^{2}-2\\!\\!\\!\\!\sum_{\begin{subarray}{c}(u,v,\lambda)\in\\\
\overrightarrow{E}(G)\setminus\overrightarrow{E}(G(x))\end{subarray}}\\!\\!\\!\\!\langle{u,v,\lambda}|{\tilde{w}}\rangle\langle{v,u,\lambda}|{\tilde{w}}\rangle\leq\left\|2\Pi_{H(x)^{\bot}}|\tilde{w}\rangle\right\|^{2},$
(87)

where the last inequality uses Cauchy-Schwarz, so $\frac{1}{2}|\theta\rangle$
is also an approximate positive witness for $x$. Similarly,

$\||\theta\rangle\|^{2}\leq\|2|\tilde{w}\rangle\|^{2},$ (88)

so $\frac{1}{2}|\theta\rangle$ is optimal.

By Claim 29, we can consider a decomposition of $|\theta\rangle$ into self-
avoiding paths $p_{i}$ and cycles $c_{i}$ such that all cycles are disjoint
from all paths,
$|\theta\rangle=\sum_{i=1}^{r}\alpha_{i}|p_{i}\rangle+\sum_{i=1}^{r^{\prime}}\beta_{i}|c_{i}\rangle$,
where for each $i$,

$\displaystyle|p_{i}\rangle=\sum_{j=1}^{L_{i}}|u^{(i)}_{j},u^{(i)}_{j+1},\lambda_{i,j}\rangle-\sum_{j=1}^{L_{i}}|u^{(i)}_{j+1},u^{(i)}_{j},\lambda_{i,j}\rangle,$
(89)
$\displaystyle|c_{i}\rangle=\sum_{j=1}^{L_{i}^{\prime}}|v^{(i)}_{j},v^{(i)}_{j+1},\lambda_{i,j}^{\prime}\rangle-\sum_{j=1}^{L_{i}^{\prime}}|v^{(i)}_{j+1},v^{(i)}_{j},\lambda_{i,j}^{\prime}\rangle$
(90)

where $v^{(i)}_{L_{j}^{\prime}+1}=v^{(i)}_{1}$ and
$\\{\lambda_{i,j}\\}_{i,j}\cap\\{\lambda_{i,j}^{\prime}\\}_{i,j}=\emptyset$.
It’s easy to see (in the case of unit edge weights) that $A|c_{i}\rangle=0$
for all $i$, so

$\displaystyle
A\frac{1}{2}\sum_{i=1}^{r}\alpha_{i}|p_{i}\rangle=A\frac{1}{2}|\theta\rangle=\tau.$
(91)

Let $|\theta^{\prime}\rangle=\sum_{i=1}^{r}\alpha_{i}|p_{i}\rangle$. Then
since $c_{i}$ and $p_{j}$ have no common edges, we have
$\langle{c_{i}}|{p_{j}}\rangle=0$, and also $\langle
c_{i}|(I-\Pi_{H(x)})|p_{j}\rangle=0$, so the error of
$\frac{1}{2}|\theta^{\prime}\rangle$ is
$\frac{1}{4}\left\|\Pi_{H(x)^{\bot}}|\theta^{\prime}\rangle\right\|^{2}\leq\frac{1}{4}\left\|\Pi_{H(x)^{\bot}}|\theta\rangle\right\|^{2}$,
so $\frac{1}{2}|\theta^{\prime}\rangle$ also has minimal error. Furthermore,
$\left\||\theta^{\prime}\rangle\right\|^{2}\leq\left\||\theta\rangle\right\|^{2}$,
with equality if and only if there are no cycles in the decomposition. By the
optimality of $\frac{1}{2}|\theta\rangle$ as an approximate positive witness
for $x$, we can conclude that
$|\theta\rangle=\sum_{i=1}^{r}\alpha_{i}|p_{i}\rangle$, and since
$A|p_{i}\rangle=2\tau$ for all $i$, and $A|\theta\rangle=2\tau$, we have
$\sum_{i=1}^{r}{\alpha_{i}}=1$. Then

$\displaystyle\left\||\theta\rangle\right\|^{2}\leq\max_{i}\left\||p_{i}\rangle\right\|^{2}=\max_{i}2L_{i}.$
(92)

Since the longest self-avoiding $st$-path in $G_{\phi}$ has length at most
$l^{0pt_{\wedge}}$, and each $L_{i}$ is the length of a self-avoiding path in
$G_{\phi}$, we have
$\tilde{w}_{+}(x,P_{G_{\phi}})\leq\frac{1}{4}2l^{0pt_{\wedge}}=\frac{1}{2}l^{0pt_{\wedge}}$.
Thus $\widetilde{W}_{+}(P_{G_{\phi}})\leq\frac{1}{2}l^{0pt_{\wedge}}$.

Next we prove the bound on $\widetilde{W}_{-}$. A min-error approximate
negative witness for $x$ in $P_{G_{\phi}}$ is a function
$\omega:V(G_{\phi})\rightarrow\mathbb{R}$ such that
$\omega\tau=\omega(s)-\omega(t)=1$, and $\left\|\omega
A\Pi_{H(x)}\right\|^{2}=\sum_{(u,v,\lambda)\in\overrightarrow{E}(G_{\phi}(x))}(\omega(u)-\omega(v))^{2}$
is minimized. By Claim 31, since $\omega\tau=1$, the function
$\theta:\overrightarrow{E}(G^{\prime}_{\phi})\rightarrow\mathbb{R}$ defined by
$\theta((u,v,\lambda)^{\dagger})=\omega(u)-\omega(v)$ is a unit
$s^{\prime}t^{\prime}$-flow on $G^{\prime}_{\phi}=G_{\phi^{\prime}}$, and the
witness complexity is

$\displaystyle\left\|\omega
A\right\|^{2}=\sum_{(u,v,\lambda)\in\overrightarrow{E}(G_{\phi})}(\omega(u)-\omega(v))^{2}=\sum_{(u^{\prime},v^{\prime},\lambda)\in\overrightarrow{E}(G^{\prime}_{\phi})}\theta(u^{\prime},v^{\prime},\lambda)^{2}=\||\theta\rangle\|^{2}$
(93)

where we create $|\theta\rangle$ from $\theta$ in the usual way. By an
argument similar to the previous argument, if $\omega$ is an optimal
approximate negative witness for $x$, then $\||\theta\rangle\|^{2}$ is upper
bounded by twice the length of the longest self-avoiding
$s^{\prime}t^{\prime}$-path in $G_{\phi}^{\prime}=G_{\phi^{\prime}}$. By Lemma
35 and Claim 43, this is upper bounded by
$2l^{0pt_{\wedge}(\phi^{\prime})}=2l^{0pt_{\vee}(\phi)}$, where
$0pt_{\wedge}(\phi^{\prime})$ is the $\wedge$-depth of $\phi^{\prime}$, and
$0pt_{\vee}=0pt_{\vee}(\phi)$ is the $\vee$-depth of $\phi$. Thus
$\tilde{w}_{-}(x,P_{G_{\phi}})\leq 2l^{0pt_{\vee}}$, and so
$\widetilde{W}_{-}\leq 2l^{0pt_{\vee}}$. ∎

###  D.3 Winning the NAND-tree

We now analyze the algorithm for winning the game associated with a nand-tree,
proving Lemma 26 and Theorem 27. See 26

###### Proof.

Since at least one of $x^{0}$ and $x^{1}$ is a 1-instance, using the
description of Select in Section 5.2, at least one of the programs will
terminate. Suppose without loss of generality that $\texttt{Est}(x^{0})$ is
the first to terminate, outputting $w_{0}$. Then there are two possibilities:
$\texttt{Est}(x^{1})$ does not terminate after $p(d)\sqrt{w_{0}}N^{1/4}$
steps, in which case, $R_{s,t}(G_{\textsc{nand}_{d}}(x^{0}))\leq
2R_{s,t}(G_{\textsc{nand}_{d}}(x^{1}))$, and Select outputs 0; or
$\texttt{Est}(x^{1})$ outputs $w_{1}$ before $p(d)\sqrt{w_{0}}N^{1/4}$ steps
have passed and Select outputs $b$ such that $w_{b}\leq w_{\bar{b}}$.

We will prove the first case by contradiction. Suppose

$\displaystyle
2R_{s,t}(G_{\textsc{nand}_{d}}(x^{1}))<R_{s,t}(G_{\textsc{nand}_{d}}(x^{0})).$
(94)

Then $\texttt{Est}(x^{1})$ must terminate after

$\displaystyle
p(d)\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x^{1}))}N^{1/4}\leq\frac{1}{\sqrt{2}}p(d)\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x^{0}))}N^{1/4}$
(95)

steps. In $\mathtt{Select}$, we run $\mathtt{Est}$ to relative accuracy
$\varepsilon=1/3$, so we have

$\displaystyle|w_{0}-R_{s,t}(G_{\textsc{nand}_{d}}(x^{0}))|\leq\frac{1}{3}R_{s,t}(G_{\textsc{nand}_{d}}(x^{0})),$
(96)

and so

$\displaystyle w_{0}\geq\frac{2}{3}R_{s,t}(G_{\textsc{nand}_{d}}(x^{0})).$
(97)

Plugging Eq. (97) into Eq. (95), we have $\texttt{Est}(x^{1})$ must terminate
after
$\frac{1}{\sqrt{2}}p(d)\sqrt{\frac{3}{2}w_{0}}N^{1/4}<p(d)\sqrt{w_{0}}N^{1/4}$
steps, which is a contradiction.

Thus, $R_{s,t}(G_{\textsc{nand}_{d}}(x^{0}))\leq
2R_{s,t}(G_{\textsc{nand}_{d}}(x^{1}))$, so outputting 0 is correct.
Furthermore, since we terminate after
$p(d)\sqrt{w_{0}}N^{1/4}=\widetilde{O}(\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x^{0}))}N^{1/4})$
steps, and since
$R_{s,t}(G_{\textsc{nand}_{d}}(x^{0}))=O(R_{s,t}(G_{\textsc{nand}_{d}}(x^{1})))$,
the running time is at most
$\widetilde{O}\left(N^{1/4}\sqrt{w_{\min}}\right)$.

We now consider the second case, in which both programs output estimates
$w_{0}$ and $w_{1}$, such that
$|w_{b}-R_{s,t}(G_{\textsc{nand}_{d}}(x^{b}))|\leq\varepsilon
R_{s,t}(G_{\textsc{nand}_{d}}(x^{b}))$ for $b=0,1$. Suppose $w_{b}\leq
w_{\bar{b}}$. We then have

$\frac{R_{s,t}(G_{\textsc{nand}_{d}}(x^{b}))}{R_{s,t}(G_{\textsc{nand}_{d}}(x^{\bar{b}}))}\leq\frac{R_{s,t}(G_{\textsc{nand}_{d}}(x^{b}))}{w_{b}}\frac{w_{\bar{b}}}{R_{s,t}(G_{\textsc{nand}_{d}}(x^{\bar{b}}))}\leq\frac{1+\varepsilon}{1-\varepsilon}=\frac{4/3}{2/3}=2.$
(98)

Thus $R_{s,t}(G_{\textsc{nand}_{d}}(x^{b}))\leq
2R_{s,t}(G_{\textsc{nand}_{d}}(x^{\bar{b}}))$, as required. Furthermore, the
running time of the algorithm is bounded by the running time of
$\texttt{Est}(x^{1})$, the second to terminate. We know that
$\texttt{Est}(x^{1})$ has running time at most
$\widetilde{O}\left(\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x^{1}))}N^{1/4}\right)$
steps, and by assumption, $\texttt{Est}(x^{1})$ terminated after less than
$p(d)\sqrt{w_{0}}N^{1/4}=\widetilde{O}\left(\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x^{0}))}N^{1/4}\right)$
steps, so the total running time is at most
$\widetilde{O}\left(N^{1/4}\sqrt{w_{\min}}\right)$. ∎

See 27

###### Proof.

First note that Player $A$ must make $O(d)$ choices over the course of the
game. We amplify Player $A$’s probability of success by repeating
$\mathtt{Select}$ at each decision node $O(\log d)$ times and taking the
majority. Then the probability that Player $A$ chooses the wrong direction at
any node is $O(1/d)$, and we ensure that her probability of choosing the wrong
direction over the course of the algorithm is $<1/3$. From here on, we analyze
the error free case.

Let $p(d)$ be a non-decreasing polynomial function in $d$ such that
$\mathtt{Select}$, on inputs $x^{0},x^{1}\in\\{0,1\\}^{2^{d}}$, terminates in
at most
$p(d)2^{d/4}\sqrt{\min\\{R_{s,t}(G_{\textsc{nand}_{d}}(x^{0})),R_{s,t}(G_{\textsc{nand}_{d}}(x^{1}))\\}}$
queries. Then we will prove that for trees of odd depth $d$, the expected
number of queries by Player $A$ over the course of the game is at most
$p(d)2^{d/4+5}\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x))}$, while for even depth
trees, it is at most
$p(d)2^{d/4+11/2}\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x))}$, thus proving the
main result.

We prove the result by induction on the depth of the tree. For depth zero
trees, there are no decisions, $N=R_{s,t}G_{\textsc{nand}_{0}}(x)=1$, so the
result holds.

For the inductive case, we treat odd and even depth cases separately. First
consider an instance of $\textsc{nand}_{d}$ with $d>0$, $d$ odd. Thus
$\textsc{nand}_{d}(x)=\textsc{nand}_{d-1}(x^{0})\wedge\textsc{nand}_{d-1}(x^{1})$,
where $x=(x^{0},x^{1})$. Because the root is at odd distance from the leaves,
the root is a decision node for Player $B$. Because we are in an $A$-winnable
tree, no matter which choice Player $B$ makes, we will end up at an
$A$-winnable subtree of depth $d-1$, so the inductive assumption holds for
those trees. That is, the expected number of queries for Player $A$ must make
to win the subtree with input $x^{b}$ (for $b\in\\{0,1\\}$) averaged over
Player $B$’s choices is at most

$\displaystyle
p(d-1)2^{(d-1)/4+11/2}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))}.$ (99)

We are assuming that Player $B$ chooses left and right with equal probability.
Thus, the expected number of queries that Player $A$ must make over Player
$B$’s choices throughout the game is at most

$\displaystyle\frac{1}{2}\Big{(}p(d-1)2^{(d-1)/4+11/2}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))}$
(100)
$\displaystyle\qquad\qquad+p(d-1)2^{(d-1)/4+11/2}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1}))}\Big{)}$
$\displaystyle\leq$ $\displaystyle
p(d-1)2^{(d-1)/4+11/2}\sqrt{\frac{1}{2}\left(R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))+R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1}))\right)}\quad\mbox{by
Jensen's ineq.,}$ $\displaystyle=$ $\displaystyle
p({d-1})2^{(d-1)/4+11/2}\sqrt{\frac{1}{2}R_{s,t}(G_{\textsc{nand}_{d}}(x))}\quad\mbox{by
Claim \ref{claim:parallel_series}},$ $\displaystyle\leq$ $\displaystyle
p\left(d\right)2^{d/4-1/4+11/2-1/2}\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x))}$
$\displaystyle\leq$ $\displaystyle
p\left(d\right)2^{d/4+5}\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x))},$

proving the case for odd $d$.

Now consider an instance of $\textsc{nand}_{d}$ with $d>0$, $d$ even. Thus
$\textsc{nand}_{d}(x)=\textsc{nand}_{d-1}(x^{0})\vee\textsc{nand}_{d-1}(x^{1})$,
where $x=(x^{0},x^{1})$. Because the root is at even distance from the leaves,
the root is a decision node for Player $A$. Player $A$ runs
$\mathtt{Select}(x^{0},x^{1})$, which returns $b\in\\{0,1\\}$ such that (by
Lemma 26)

$\displaystyle R_{s,t}(G_{\textsc{nand}^{d-1}}(x^{b}))\leq
2R_{s,t}(G_{\textsc{nand}^{d-1}}(x^{\bar{b}})),$ (101)

which requires at most

$\displaystyle\min_{b^{*}\in\\{0,1\\}}p\left({d-1}\right)2^{(d-1)/4}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b^{*}}))}$
(102)

queries.

After making the choice to move to the subtree with input $x^{b}$, by the
inductive assumption, the expected number of queries that Player $A$ need to
make throughout the rest of the game (averaged over Player $B$’s choices) is

$\displaystyle
p\left({d-1}\right)2^{d/4+5}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))}.$
(103)

There are two cases to consider. If
$R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))\leq
R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{\bar{b}}))$, then combining Eq. (102) and
Eq. (103), we have that the total number of queries averaged over Player $B$’s
choices is

$\displaystyle
p\left({d-1}\right)2^{(d-1)/4}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))}+p\left({d-1}\right)2^{(d-1)/4+5}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))}$
$\displaystyle\leq$ $\displaystyle
p\left({d-1}\right)2^{(d-1)/4}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))}(1+2^{5})$
$\displaystyle\leq$ $\displaystyle
p\left({d-1}\right)2^{(d-1)/4+5+1/16}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))}$
$\displaystyle\leq$ $\displaystyle
p\left({d-1}\right)2^{(d-1)/4+5+1/16+1/2}\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x))}$
$\displaystyle\leq$ $\displaystyle
p\left(d\right)2^{d/4+11/2}\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x))}$ (104)

where we’ve used
$R_{s,t}(G_{\textsc{nand}_{d}}(x))=\left({R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))}^{-1}+{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1}))}^{-1}\right)^{-1}$
from Claim 5 and the fact that $R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))\leq
R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{\bar{b}}))$ to bound the value
$R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))$ by
$2R_{s,t}(G_{\textsc{nand}_{d}}(x))$. This proves the even induction step for
this case.

The other case is if
$R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))>R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{\bar{b}}))$.
In that case, again using the fact that
$R_{s,t}(G_{\textsc{nand}_{d}}(x))=\left({R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{0}))}^{-1}+{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{1}))}^{-1}\right)^{-1}$,
we have

$R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{\bar{b}}))=R_{s,t}(G_{\textsc{nand}_{d}}(x))\left(1+\frac{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{\bar{b}}))}{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{{b}}))}\right)^{-1}\leq\frac{2}{3}R_{s,t}(G_{\textsc{nand}_{d}}(x)),$
(105)

where the inequality follows from Eq. (101). Thus, the average total number of
queries is

$\displaystyle
p\left({d-1}\right)2^{(d-1)/4}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{\bar{b}}))}+p\left({d-1}\right)2^{(d-1)/4+5}\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{b}))}$
$\displaystyle\leq$ $\displaystyle
p(d-1)2^{(d-1)/4}\left(\sqrt{R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{\bar{b}}))}+2^{5}\sqrt{2R_{s,t}(G_{\textsc{nand}_{d-1}}(x^{\bar{b}}))}\right)$
$\displaystyle\leq$ $\displaystyle
p(d-1)2^{(d-1)/4}(1+2^{5+1/2})\sqrt{\frac{2}{3}R_{s,t}(G_{\textsc{nand}_{d}}(x))}$
$\displaystyle\leq$ $\displaystyle
p(d)2^{d/4-1/4+5}\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x))}$ $\displaystyle\leq$
$\displaystyle p(d)2^{d/4+5}\sqrt{R_{s,t}(G_{\textsc{nand}_{d}}(x))}.$ (106)

This proves the induction step for the other case. ∎


* Wattenberg et al. (2016) Martin Wattenberg, Fernanda Viégas, and Ian Johnson.  How to use t-SNE effectively.  _Distill_ , 1(10):e2, 2016.
  * Weathers et al. (2013) Frank W Weathers, Brett T Litz, Terence M Keane, Patrick A Palmieri, Brian P Marx, and Paula P Schnurr.  The PTSD checklist for DSM-5 (PCL-5) – standard [measurement instrument].  _Scale available from the National Center for PTSD at www. ptsd. va. gov_ , 10, 2013.
  * Weinberger and Saul (2009) Kilian Q Weinberger and Lawrence K Saul.  Distance Metric Learning for Large Margin Nearest Neighbor Classification.  _Journal of Machine Learning Research_ , 10(2), 2009.
  * Wexler (2017) Rebecca Wexler.  When a computer program keeps you in jail: How computers are harming criminal justice.  _New York Times_ , June 13 2017.
  * Wood (2017) Simon N Wood.  _Generalized additive models: an introduction with R_.  CRC press, 2017.
  * Wu and Tabak (2017) Chenyue Wu and Esteban G Tabak.  Prototypal Analysis and Prototypal Regression.  _arXiv e-print arXiv:1701.08916_ , 2017.
  * Xie et al. (2020) Feng Xie, Bibhas Chakraborty, Marcus Eng Hock Ong, Benjamin Alan Goldstein, and Nan Liu.  Autoscore: A machine learning–based automatic clinical score generator and its application to mortality prediction using electronic health records.  _JMIR Med Inform_ , 8(10):e21798, October 2020\.
  * Yang et al. (2017) Hongyu Yang, Cynthia Rudin, and Margo Seltzer.  Scalable bayesian rule lists.  In _Proceedings of International Conference on Machine Learning (ICML)_ , pages 3921–3930. PMLR, 2017.
  * Yang and Perdikaris (2019) Yibo Yang and Paris Perdikaris.  Conditional deep surrogate models for stochastic, high-dimensional, and multi-fidelity systems.  _Computational Mechanics_ , 64(2):417–434, 2019\.
  * Yang et al. (2018) Yongxin Yang, Irene Garcia Morillo, and Timothy M Hospedales.  Deep neural decision trees.  _arXiv preprint arXiv:1806.06988_ , 2018.
  * Yin and Yu (2017) Junming Yin and Yaoliang Yu.  Convex-constrained sparse additive modeling and its extensions.  _arXiv e-print arXiv:1705.00687_ , 2017.
  * Yin and Han (2003) Xiaoxin Yin and Jiawei Han.  Cpar: Classification based on predictive association rules.  In _Proceedings of the 2003 SIAM International Conference on Data Mining (SDM)_ , pages 331–335. SIAM, 2003.
  * Yu et al. (2019) Chao Yu, Jiming Liu, and Shamim Nemati.  Reinforcement learning in healthcare: A survey.  _arXiv e-print arXiv:1908.08796_ , 2019.
  * Yu et al. (2020a) Jinqiang Yu, Alexey Ignatiev, Pierre Le Bodic, and Peter J Stuckey.  Optimal decision lists using sat.  _arXiv e-print arXiv:2010.09919_ , 2020a.
  * Yu et al. (2020b) Jinqiang Yu, Alexey Ignatiev, Peter J Stuckey, and Pierre Le Bodic.  Computing optimal decision sets with sat.  In _International Conference on Principles and Practice of Constraint Programming_ , pages 952–970. Springer, 2020b.
  * Zahavy et al. (2016) Tom Zahavy, Nir Ben-Zrihem, and Shie Mannor.  Graying the black box: Understanding DQNs.  In _International Conference on Machine Learning_ , pages 1899–1908. PMLR, 2016.
  * Zambaldi et al. (2018) Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, et al.  Relational deep reinforcement learning.  _arXiv e-print arXiv:1806.01830_ , 2018.
  * Zech et al. (2018) John R. Zech et al.  Variable generalization performance of a deep learning model to detect pneumonia in chest radiographs: A cross-sectional study.  _PLoS Med._ , 15(e1002683), 2018.
  * Zhang et al. (2021) Kristine Zhang, Yuanheng Wang, Jianzhun Du, Brian Chu, Leo Anthony Celi, Ryan Kindle, and Finale Doshi-Velez.  Identifying decision points for safe and interpretable reinforcement learning in hypotension treatment.  _arXiv e-print arXiv:2101.03309_ , 2021.
  * Zhang et al. (2018) Quanshi Zhang, Ying Nian Wu, and Song-Chun Zhu.  Interpretable convolutional neural networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 8827–8836, 2018.
  * Zhang et al. (2019) Yujia Zhang, Kuangyan Song, Yiming Sun, Sarah Tan, and Madeleine Udell.  “Why should you trust my explanation?” Understanding uncertainty in LIME explanations.  In _Proceedings of the International Conference on Machine Learning AI for Social Good Workshop_ , 2019.
  * Zhao et al. (2011) Hongxu Zhao, Ran Jin, Su Wu, and Jianjun Shi.  PDE-constrained gaussian process model on material removal rate of wire saw slicing process.  _Journal of Manufacturing Science and Engineering_ , 133(2), 2011.
  * Zhou et al. (2014) Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba.  Object detectors emerge in deep scene CNNs.  In _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2014.
  * Zhou et al. (2018a) Bolei Zhou, David Bau, Aude Oliva, and Antonio Torralba.  Interpreting deep visual representations via network dissection.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2018a.
  * Zhou et al. (2018b) Bolei Zhou, Yiyou Sun, David Bau, and Antonio Torralba.  Interpretable basis decomposition for visual explanation.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 119–134, 2018b.
  * Zhou (2002) Ding-Xuan Zhou.  The covering number in learning theory.  _Journal of Complexity_ , 18(3):739–767, 2002\.
  * Zhu et al. (2019) Yinhao Zhu, Nicholas Zabaras, Phaedon-Stelios Koutsourelakis, and Paris Perdikaris.  Physics-constrained deep learning for high-dimensional surrogate modeling and uncertainty quantification without labeled data.  _Journal of Computational Physics_ , 394:56–81, 2019.
  * Zhu et al. (2014) Zhenyao Zhu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.  Multi-view perceptron: a deep model for learning face identity and view representations.  In _Proceedings of Neural Information Processing Systems (NeurIPS)_ , pages 217–225, 2014.