Polynomial Size, Short-Circuit Resilient Circuits for NC

Computation and communication have a deep connection. Just like prior work [18, 4, 7], the current work also exploits this connection via the Karchmer-Wigderson transformation. Specifically, Karchmer and Wigderson [19] show that any circuit computing a function $f$ can be converted into a communication protocol for a related search problem ${\mathrm{𝖪𝖶}}_f$ such that the depth of the circuit matches the length of the communication protocol, and vice versa. An analogous transformation can be shown in the reverse direction, i.e. a transformation that takes error-resilient communication protocols to error resilient circuits, and was used in [18, 4] to build error resilient formulas.

The Karchmer-Wigderson transformation does not preserve the size of the circuit and in fact, blows it up to be exponential in the depth. To circumvent this blowup in size, [25, 29] showed how to convert any circuit into a “dag-protocol” that preserves both its size and depth. dag-protocols are a generalization of communication protocols, and can be represented by the following pebble game: There is a rooted directed acyclic graph, and each non-sink node in the graph belongs to one of the two parties, while each sink node is associated with an output. The game starts with a “pebble” at the root of graph, that is moved along the edges of the graph. At every step, if the pebble is not already at a sink node, the party who owns that node will move the pebble along one of its out-edges. This will end when the pebble reaches a sink node, and the output will be the output of the sink node.

[25, 29] showed that every circuit computing a function $f$ can be converted to a dag-protocol with the same size and depth that solves ${\mathrm{𝖪𝖶}}_f$ with a strong correctness guarantee called rectangular correctness (see Definition 5 for a precise definition). The reverse direction also holds, and in fact even holds in the error-resilient setting. This direction was used to get error-resilient circuits from error-resilient dag-protocols in [7]. We adopt a similar approach and use the [25, 29] transformation to go from circuits to dag-protocols and back. Indeed, our main technical result is the following theorem about error-resilient dag-protocols.

Even though the short-circuit error model we consider is the most studied one, other models have also been considered. For example, von Neumann [30] initiated the study of the stochastic noise model, where the noise flips the value of each gate in the circuit independently with some small fixed probability. Von Neumann’s model was studied by a long sequence of works, including [6, 22, 23, 11, 8, 9, 17, 13, 12, 10]. In this model, it is known that a circuit of size $s$ can converted to a noise resilient circuit of size $O(s\log s)$, and that a function with sensitivity $s^{\prime }$ requires a resilient circuits of size $\mathrm{\Omega }(s^{\prime }\log s^{\prime })$ [30, 6, 22, 13, 12].

In this paper, we study the short-circuit error model of [20] but there is also a different adversarial model studied by [14], where the adversary may corrupt the output of a small constant fraction of the gates at each layer of the circuit in an arbitrary way. They show how to construct error resilient circuits for symmetric functions in this model, by exploiting interesting connections between their model and probabilistically checkable proofs. However, the obtained circuit is only guaranteed to compute, what they call, a “loose version” of the function, and may err on many inputs. Lastly, we mention the orthogonal direction of constructing testable circuits which are circuits on which errors can detected (but not necessarily corrected) efficiently [2, 1].

As our work develops error-resilient circuits via error-resilient dag-protocols, it is also connected with the vast literature on codes for interactive communication, or simply “interactive codes”, that are used to make communication protocols resilient to noise. This field, initiated by the seminal works [26, 27, 28] has received a lot of attention over the last three decades, and various aspects of interactive codes have been extensively studied. A work loosely related to circuits is [5] but see [16] for an excellent survey. We note that all constructions of error resilient dag-protocols are heavily inspired by an underlying interactive coding scheme (recall that dag-protocols are a generalization of communication protocols).

Razborov [25] introduced a model of PLS communication protocols, and used it generalize the Karchmer-Wigderson transformation [19] in a way that preserves both the size and the depth of the circuit. This connection was used by Krajícek [21], who introduced the technique of monotone feasible interpolation, which became a popular method for proving lower bounds on the refutation size in propositional proof systems such as Resolution, and Cutting Planes [3], by reducing to monotone circuit lower bounds. The notion of PLS communication protocols was simplified by Pudlak [24] and Sokolov [29] to the notion of dag-like communication protocols, which we call dag-protocols. Subsequently, a “converse” to monotone feasible interpolation was established in [15] to prove new lower bounds on monotone circuits by lifting lower bounds on Resolution refutations. To the best of our knowledge, our work is the only work, other than [7], to use the notion of dag-protocols in a “positive” manner, namely to construct error-resilient circuits, in contrast to prior work which mainly used this notion to prove lower bounds in proof complexity and circuit complexity.

We devise a way to make dag-protocols corresponding to ${\mathrm{𝖭𝖢}}^1$ circuits resilient while remembering only a constant number (in fact, $2$) states at each point, at the cost of blowing up the number of layers exponentially. As the depth of ${\mathrm{𝖭𝖢}}^1$ circuits is logarithmic in $n$, this exponential blowup is still polynomial in $n$. Moreover, as we only remember a constant number of states at each point, the blowup in the size of each layer is also polynomial, and combining this with the blowup in the number of layers still gives a polynomial blowup.

Note that any protocol must at least remember the current state, and thus a protocol that remembers only $2$ states actually remembers only $1$ extra state! Interestingly, for our protocol, this extra state is not a state in the past but actually the next state in the future that the protocol is considering going to. Specifically, if the protocol is currently in state in layer $i-1$ (for some $i>0$), and wants to advance to a state in layer $i$, then instead of jumping to that state directly, it is remembered as a “candidate” state until the protocol has enough “confidence” in the candidate to advance. This confidence is implemented via a variable $\mathrm{𝚌𝚗𝚏}$ that is incremented every time the parties want to advance and decremented every time they suspect that the states in memory are incorrect. Only after the confidence $\mathrm{𝚌𝚗𝚏}$ hits a certain threshold ${ℭ}_i$ does the protocol actually advance to the state in layer $i$.

We will view the thresholds as being cumulative, i.e., ${ℭ}_i$ is the total confidence required to go from layer $0$ to layer $i$. This means that ${ℭ}_i-{ℭ}_{i-1}$ is the additional confidence needed to advance from layer $i-1$ to layer $i$. With this said, the obvious question is how large does ${ℭ}_i-{ℭ}_{i-1}$ need to be? In other words, how much confidence should the protocol have in the candidate before they advance to a state in layer $i$? To answer this question, one needs to consider the total “loss” of the protocol in case it advances wrongly and reaches an incorrect state. As no state in the past is remembered, the only way the protocol can recover from this incorrect state is if it starts all over again and reaches the state in layer $i-1$, which requires a total increase in confidence of ${ℭ}_{i-1}$. Thus, the increase (which equals ${ℭ}_i-{ℭ}_{i-1}$) of the confidence required to jump from layer $i-1$ to layer $i$ should be the same order of magnitude as the confidence ${ℭ}_{i-1}$ needed to reach layer $i-1$ from the beginning of the protocol. Solving, we get that ${ℭ}_i$ should be (at least) exponential in $i$. This is the choice that we make, setting ${ℭ}_i=c^i$ for some suitable constant $c>1$.

We now provide more details of our protocol and argue its correctness. The protocol starts at the initial (root) node in layer $0$ with confidence $\mathrm{𝚌𝚗𝚏}={ℭ}_0=0$. At any given time, the protocol is in some layer, say layer $i-1$ with some confidence $\mathrm{𝚌𝚗𝚏}$, and trying to continue the simulation from some state in this layer. For this, the protocol first checks⁶⁶6As in prior work, assuming that the original dag-protocol is rectangular correct is crucial for the protocol to be able to check whether or not there are errors. As this is not a novel idea for the current work, we omit a precise description in this sketch. (Very) roughly speaking (see formal definition in Definition 5), a state is said to be rectangular correct for inputs $x$ and $y$ for Alice and Bob respectively, if there exists inputs $x^{\prime }$ for Alice and $y^{\prime }$ for Bob such that the protocol reaches that state when executed with inputs $x$ and $y^{\prime }$ and also reaches it with inputs $x^{\prime }$ and $y$. This means that the parties can go over all possible inputs of the other party in order to check if the state is (rectangular) correct or not. if the current state has any errors. If so, the protocol decreases the confidence $\mathrm{𝚌𝚗𝚏}$ by $1$. This may cause $\mathrm{𝚌𝚗𝚏}$ to hit $0$, which is taken as a signal to forget all progress and restart the simulation. If no errors are found, then the current state is assumed to be correct and the action to be taken is determined by the value of the confidence $\mathrm{𝚌𝚗𝚏}$.

If we have , then it must be the case that the confidence was decreased after reaching layer $i-1$. The protocol simply increases it by $1$ trying to get it back to ${\mathrm{𝚌𝚗𝚏}}_{i-1}$ so that further progress can be made. If the confidence $\mathrm{𝚌𝚗𝚏}={ℭ}_{i-1}$, the confidence in layer $i-1$ is high enough for the protocol to compute a candidate in layer $i$. A candidate $\mathrm{𝚗𝚡𝚝}$ for the state to advance to is computed and the confidence is further increased by $1$.

Finally, if the confidence $\mathrm{𝚌𝚗𝚏}>{ℭ}_{i-1}$, then the protocol must already have a candidate $\mathrm{𝚗𝚡𝚝}$ that it is considering going to. The protocol then checks if this candidate was caused due to errors, and if so, decreases the confidence by $1$. If the confidence is lowered all the way back to ${ℭ}_{i-1}$, the protocol “forgets” about the candidate $\mathrm{𝚗𝚡𝚝}$ (and will compute a new one in the future if needed). On the other hand, if the candidate $\mathrm{𝚗𝚡𝚝}$ was not due to errors, the protocol increases the confidence $\mathrm{𝚌𝚗𝚏}$ by $1$. If this increased confidence reaches ${\mathrm{𝚌𝚗𝚏}}_i$, it is high enough to advance. The protocol forgets about the current state in layer $i-1$ and continue the rest of the simulation from the state $\mathrm{𝚗𝚡𝚝}$ in layer $i$.

We now show that the above protocol indeed simulates the original protocol correctly. For this, we first show that if the protocol has high confidence at the end of the protocol, specifically, if $\mathrm{𝚌𝚗𝚏}\ge {ℭ}_d$, where $d$ is the total number of layers (depth) of the original protocol, then the output of the protocol must be correct. Indeed, if the confidence is that high, the protocol is in a state in layer $d$ or higher⁷⁷7We append the original protocol with dummy states to get states beyond layer $d$., and the only reason this state would not be correct is if the protocol advanced to it incorrectly. However, this means that there must have been at least ${ℭ}_d-{ℭ}_{d-1}$ errors while this state was the next candidate. As the confidence thresholds are exponential, we have that the total number of errors is at least ${ℭ}_d-{ℭ}_{d-1}=\mathrm{\Omega }\left({ℭ}_d\right)$, which is more than a constant fraction and therefore, unaffordable.

Now, all we need to show is that the confidence is indeed high at the end of the protocol. For this, we fix any execution of the protocol and partition the rounds into rounds where the protocol wants to “go back” and decrease the confidence $\mathrm{𝚌𝚗𝚏}$ (this happens when either the current state or the next state $\mathrm{𝚗𝚡𝚝}$ has any errors) and rounds where it does not. We collect the former type of rounds in the set $\mathrm{𝖡𝖺𝖼𝗄}$. By definition, the confidence will increase in any round not in $\mathrm{𝖡𝖺𝖼𝗄}$ unless there are errors, and will decrease in any round in $\mathrm{𝖡𝖺𝖼𝗄}$ unless there are errors. As the total number of errors is only a small constant fraction, this means that all we need to do to show that the confidence is high at the end of the protocol is to show that the size of $\mathrm{𝖡𝖺𝖼𝗄}$ is small.

To show this, we argue that the size of $\mathrm{𝖡𝖺𝖼𝗄}$ is at most a constant factor more than the number of rounds in $\mathrm{𝖡𝖺𝖼𝗄}$ where the protocol did not go back. To see why, note that the first round in $\mathrm{𝖡𝖺𝖼𝗄}$ must be a round where the protocol added an incorrect next state as their candidate $\mathrm{𝚗𝚡𝚝}$. As mentioned above, if the next state is in layer $i$, this only happens when the confidence is exactly ${ℭ}_{i-1}$.

As long as the protocol does not advance to this next state (in other words, it remains a candidate), the confidence must stay above ${ℭ}_{i-1}$, as otherwise the protocol will forget the incorrect candidate and look for a new one. This means that the total number of rounds where the protocol does not go back and increase the confidence exceeds the total number of rounds where the protocol did go back, and we are done. On the other hand, if the protocol does advance to the candidate, there must have been at least ${ℭ}_i-{ℭ}_{i-1}$ errors, and by definition of $ℭ$, these are high enough (up to constant factors) for ${ℭ}_i$ rounds of progress. Thus, the protocol can wait until the confidence hits $0$ and restart the simulation from there.

We are yet to specify the precise increase in confidence (which equals ${ℭ}_i-{ℭ}_{i-1}$) required to advance to a state in layer $i$. For this, we look at the representation of $i$ as an integer⁸⁸8The actual proof uses the representation of $i-1$ for technical reasons. in base $\log s$. If $a_1,a_2,\mathrm{\dots }$ are the digits in this representation, we set ${ℭ}_i-{ℭ}_{i-1}$ to be proportional to $c^{{\sum }_i{a}_i}$. As there is a meeting point in memory for every power of $\log s$, it can be seen that $c^{{\sum }_i{a}_i}$ takes into account the distance from all the meeting points stored in memory, while maintaining the exponential growth required between two meeting points. We defer the remaining details to the proof.

Just like prior work, for Step $2$ above to work, it is crucial that our simulation protocol is rectangular correct, which is a stronger notion of correctness than standard correctness, and is necessary for Step $3$ to work. Without going into the precise definition, this means that we need to account for the errors in the rounds where the parties (Alice and Bob) are talking separately. That is, the errors in rounds where Alice is talking cannot be used to offset the rounds where Bob is going back and decreasing the confidence, and vice versa.

Other than doubling the notation we use (e.g., we now need to remember a pair of meeting points, one for Alice and one for Bob, etc.), this also introduces a more subtle challenge regarding the fraction of errors that we can be resilient to. To understand this, recall that the layers in the original circuit, and therefore the layers in the original dag-protocol, are alternating. This means that the party controlling the layer changes every time the protocol advances a layer. Now, imagine what happens when the adversary spends ${ℭ}_i-{ℭ}_{i-1}$ errors in a layer controlled by Alice to advance it incorrectly to a layer controlled by Bob.

As the errors for the both the parties are accounted for separately, Bob cannot detect and correct these errors, and the protocol will run as if there were no errors till the next time Alice gets to speak. This happens only after ${ℭ}_{i+1}-{ℭ}_i$ rounds, which due to our definition of $ℭ$, may be a factor of $c$ larger than ${ℭ}_i-{ℭ}_{i-1}$, the total number of errors inserted by the adversary. Thus, it is possible for the adversary to waste $c$ rounds of simulation per error, implying that there has to be a multiplicative $1/c$ loss in the overall error resilience. Moreover, $c$ cannot be too small, as then the parties will not be able to correctly maintain their meeting points. We are able to show that this loss is a constant proportional to the total number of meeting points; see the formal version of our main theorem (Theorem 8).

We will consider Boolean circuits with negations at the inputs. That is, a Boolean circuit will be a directed acyclic graph $C$ where each non-source node (or gate) is labelled as an $\wedge$ gate or an $\vee$ gate, while each source node is labelled with an input variable or the negation of the input variable. The source nodes are also called input gates and one designated node in $C$ is called the output gate. We use $V_{\wedge }$ and $V_{\vee }$ to denote the set of all the nodes in $C$ that are labelled $\wedge$ and $\vee$ respectively. We define how computation over a circuit $C$ takes place by inductively defining the functions $f_{C,v}$ computed at each gate $v$. We have:

When $v$ is the output gate, we omit it from the notation and simply write $f_C$, which we call the function computed by $C$. We will assume that every gate in $C$ that is not an input gate has at least one edge coming to it. We define the size of $C$ to be the number of nodes in $C$ and the depth of $C$ to be the length of the longest path in $C$ starting from an input gate and ending at the output gate. We use $\Vert C\Vert$ to denote the size of $C$.

Note that edges in $C$ are going “up” from the inputs to the output gate. This contrasts with the edges in dag-protocols that are going “down” from the root to the leaves as defined below. These two directions, although different, follow the conventions for both circuits and dag-protocols.

Let $𝒳$ and $𝒴$ be input sets for Alice and Bob respectively and $𝒪$ be a set of outputs. A search problem on these input and output sets is defined by a relation $S\subseteq 𝒳\times 𝒴\times 𝒪$, and the goal of Alice and Bob is to determine, given inputs $x\in 𝒳$ and $y\in 𝒴$ respectively, an element $o\in 𝒪$ such that $(x,y,o)\in S$.

KW-games are special type of search problems that are defined using a Boolean function $f$ on $n$ variables (for some $n$). Here, the set $𝒳$ is the set $f^{-1}(1)$ of all inputs for which $f$ evaluates to $1$, $𝒴$ is the set $f^{-1}(0)$ of all inputs for which $f$ evaluates to $0$, and $𝒪$ is the set $[n]$. As $𝒳$ and $𝒴$ are disjoint by definition, for any $x\in 𝒳$, $y\in 𝒴$, there exists $o\in [n]$ such that $x_o\ne y_o$. The search problem ${\mathrm{𝖪𝖶}}_f$ is the problem of finding such an $o$, namely, it is the subset:

We now define the notion of dag-protocols. Let $𝒳$, $𝒴$, and $𝒪$ be input and output sets as above. A dag-protocol is defined by a tuple:

Here, $G$ is a directed acyclic graph with vertices partitioned into $V_A$, $V_B$, and $V_O$ respectively, and edges $E$. We will use $V=V_A\cup V_B\cup V_O$ to be the set of all vertices in $G$ and $\mathrm{𝗋𝗍}\in V$ is a special vertex called the root. For all $v\in V_A$, the function $h_v$ is a “message function” that maps Alice’s input set $𝒳$ to a vertex in $V$ that $v$ has an edge to. Similarly, for all $v\in V_B$, the function $h_v$ maps Bob’s input set $𝒴$ to a vertex in $V$ that $v$ has an edge to. We often conflate the two and write $h_v:𝒳\times 𝒴\to V$ with the understanding that the second argument is redundant if $v\in V_A$ and the first argument is redundant if $v\in V_B$. Finally, for all $v\in V_O$, the value $o_v\in 𝒪$ is the output value for the vertex $v$. We will assume that vertices in $V_O$ do not have any out-edges, all other vertices have at least one outgoing edge (as otherwise the message functions will not be defined) and $\mathrm{𝗋𝗍}$ does not have any incoming edges. We define the size of $\mathrm{\Pi }$ to be $\left|V\right|$, the number of nodes in $\mathrm{\Pi }$, and the depth of $\mathrm{\Pi }$ to be the length of the longest path in $G$ starting from $\mathrm{𝗋𝗍}$. We use $\Vert \mathrm{\Pi }\Vert$ to denote the size of $\mathrm{\Pi }$.

As mentioned above, edges in a dag-protocol go “down” from the root to the leaves, and are thus opposite to our convention for circuits. We are explicit about the direction in our exposition whenever there is room for ambiguity.

A dag-protocol $\mathrm{\Pi }$ as above is executed by start with inputs $x\in 𝒳$, $y\in 𝒴$ and a vertex $v=\mathrm{𝗋𝗍}$, and continuing as follows: If $v\in V_A\cup V_B$ then the execution simply uses the message function and updates the current vertex to $h_v(x,y)$⁹⁹9Recall that $h_v(x,y)$ is independent of $y$ if $v\in V_A$ and is independent of $x$ if $v\in V_B$.. Otherwise, we have $v\in V_O$, and the execution terminates with the output $o_v$. As this output is determined by $x$ and $y$, we will denote it using $\mathrm{\Pi }(x,y)$. For a search problem $S\subseteq 𝒳\times 𝒴\times 𝒪$, we say that $\mathrm{\Pi }$ solves $S$ if for all $x\in 𝒳$, $y\in 𝒴$, we have $(x,y,\mathrm{\Pi }(x,y))\in S$.

We consider short-circuit errors. Let $C$ be a Boolean circuit as above. An error pattern for $C$ is defined by a function $e:V\to V\cup \{\ast \}$ satisfying the property that $e(v)$ maps $v$ to an in-neighbor of $v$, i.e. to a neighbor of $v$ that is “below” it, or to $\ast$, for all $v\in V$. In particular, if $v\notin V_{\wedge }\cup V_{\vee }$, we have $e(v)=\ast$. It will often be convenient to separate $e$ into two functions and write $e=(e_{\vee },e_{\wedge })$, where $e_{\vee }$ is the function $e$ restricted to the vertices in $V_{\vee }$ and $e_{\wedge }$ is the function $e$ restricted to the vertices in $V_{\wedge }$. Let $C$ be a circuit and $e$ be an error pattern for $C$. Let $v\in C$ be a gate. We define how computation takes place in $C$ in the presence of errors $e$ by inductively defining the functions $f_{C,e,v}$ computed at each gate $v$. We have¹²¹²12Recall that the label of an input gate is either an input variable or the negation of an input variable.:

We omit $v$ from the notation if $v$ is the output gate of $C$. Let $C$ be a circuit and $ℰ$ be a set of error patterns for $C$. For a function $f$, we say that $C$ computes $f$ despite $ℰ$, if for all $e\in ℰ$, we have $f_{C,e}=f$. We say that $ℰ$ is rectangular if viewing every $e\in ℰ$ as a pair $e=(e_{\vee },e_{\wedge })$ gives a combinatorial rectangle. When this happens, we use ${ℰ}_{\vee }$ to denote the projection of this rectangle on the first coordinate and ${ℰ}_{\wedge }$ to denote the projection on the second coordinate (thus, $ℰ={ℰ}_{\vee }\times {ℰ}_{\wedge }$)

We now define the set of error patterns that we work with. Let $\mathrm{\Theta }\ge 0$ be an integer parameter. For a circuit $C$, define the set ${ℰ}_{\mathrm{\Theta }}\left(C\right)$ to be the set of all error patterns $e$ such that for any path in $C$ that starts at an input gate and ends the output gate, at most $\mathrm{\Theta }$ gates $v\in V_{\wedge }$ on the path satisfy $e(v)\ne \ast$ and at most $\mathrm{\Theta }$ gates $v\in V_{\vee }$ on the path satisfy $e(v)\ne \ast$. Observe that the set ${ℰ}_{\mathrm{\Theta }}\left(C\right)$ is rectangular for all $\mathrm{\Theta }\ge 0$.

Let $\mathrm{\Pi }$ be a dag-protocol as above. An error pattern $\xi$ for $\mathrm{\Pi }$ is defined by a function $\xi :V\to V\cup \{\ast \}$ satisfying the property that $\xi (v)$ maps $v$ to an out-neighbor of $v$, i.e. to a neighbor of $v$ that is “below” it¹³¹³13Recall that our conventions for the directions of edges in circuits is opposite that in dag-protocols., or to $\ast$. In particular, if $v\in V_O$, we have $\xi (v)=\ast$. It will often be convenient to separate $\xi$ into two functions $\xi =({\xi }_A,{\xi }_B)$, where ${\xi }_A$ is the function $\xi$ restricted to the vertices in $V_A$, and ${\xi }_B$ is the function $\xi$ restricted to the vertices in $V_B$. The error pattern $\xi$ affects the execution of $\mathrm{\Pi }$ as follows: If the current vertex is $v$ and $\xi (v)=\ast$, the execution proceeds as before. On the other hand, if $\xi (v)\ne \ast$ (observe that this can only happen if $v\in V_A\cup V_B$), the execution updates the current vertex to $\xi (v)$ instead of updating using the function $h_v$ as before.

Let $\mathrm{\Pi }$ be a dag-protocol and $\mathrm{\Xi }$ be a set of error patterns for $\mathrm{\Pi }$. Similarly to before, we say that $\mathrm{\Xi }$ is rectangular if viewing every $\xi \in \mathrm{\Xi }$ as a pair $\xi =({\xi }_A,{\xi }_B)$ gives a combinatorial rectangle. When this happens, we use ${\mathrm{\Xi }}_A$ to denote the projection of this rectangle on the first coordinate and ${\mathrm{\Xi }}_B$ to denote the projection on the second coordinate (thus, $\mathrm{\Xi }={\mathrm{\Xi }}_A\times {\mathrm{\Xi }}_B$). For a rectangular $\mathrm{\Xi }$, define the dag-protocol ${\mathrm{\Pi }}_{\mathrm{\Xi }}$ to be the same as $\mathrm{\Pi }$ except that the input sets are now $𝒳\times {\mathrm{\Xi }}_A$ and $𝒴\times {\mathrm{\Xi }}_B$ and the message functions $h_{\mathrm{\Xi },v}$ are defined as (recall that $\xi =({\xi }_A,{\xi }_B)$):

For a search problem $S\subseteq 𝒳\times 𝒴\times 𝒪$ and a rectangular $\mathrm{\Xi }$, we say that $\mathrm{\Pi }$ solves $S$ with rectangular correctness despite $\mathrm{\Xi }$ if ${\mathrm{\Pi }}_{\mathrm{\Xi }}$ solves $S_{\mathrm{\Xi }}$ with rectangular correctness, where $S_{\mathrm{\Xi }}\subseteq \left(𝒳\times {\mathrm{\Xi }}_A\right)\times \left(𝒴\times {\mathrm{\Xi }}_B\right)\times 𝒪$ is the search problem satisfying $((x,{\xi }_A),(y,{\xi }_B),o)\in S_{\mathrm{\Xi }}\iff (x,y,o)\in S$ for all values of $x,y,o,{\xi }_A,{\xi }_B$.

We now define the set of error patterns that we work with. Let $\mathrm{\Theta }\ge 0$ be an integer parameter. For a dag-protocol $\mathrm{\Pi }$, define the set ${\mathrm{\Xi }}_{\mathrm{\Theta }}\left(\mathrm{\Pi }\right)$ to be the set of all error patterns $\xi$ such that for any path in $G$ that starts at $\mathrm{𝗋𝗍}$ and ends at a node in $V_O$, at most $\mathrm{\Theta }$ nodes $v\in V_A$ on the path satisfy $\xi (v)\ne \ast$ and at most $\mathrm{\Theta }$ nodes $v\in V_B$ on the path satisfy $\xi (v)\ne \ast$. Observe that the set ${\mathrm{\Xi }}_{\mathrm{\Theta }}\left(\mathrm{\Pi }\right)$ is rectangular for all $\mathrm{\Theta }\ge 0$. For convenience, we will often abbreviate ${\mathrm{\Pi }}_{{\mathrm{\Xi }}_{\mathrm{\Theta }}\left(\mathrm{\Pi }\right)}$ to ${\mathrm{\Pi }}_{\mathrm{\Theta }}$.