The long code of a Boolean word $x\in\{0,1\}^w$ is its evaluation table: at the coordinate indexed by a Boolean function $g$, it stores $g(x)$. A purported long code is an arbitrary table of the same shape.

The complete nonadaptive test chooses $s$ Boolean functions $f_i$. After reading their table entries $a_i=A(f_i)$, it checks $A(B\circ f)=B(a)$ for every Boolean predicate $B$ of $s$ bits. Only the initial $s$ answers are free: they determine every checked answer. These are the long code of Section 3 and the CNA test of Section 4 of Håstad's paper, written with Boolean values instead of signs.

With a side condition $h$, the test additionally checks that each queried answer is unchanged when its function is replaced by any function agreeing with it on the set where $h$ is true. This is step (3) of the test preceding Theorem 4.17. The definitions below describe a fixed choice of the functions; the probabilistic soundness estimates are separate statements.