Proof. Removing labels preserves agreement and can only shrink the scope union. Every constraint internal to the smaller union was therefore satisfied before removal. This proves heredity. Every singleton belongs to \(\mathcal I\) by the definition of a valid query label. The maximum of absolute linear forms is absolutely homogeneous and satisfies the triangle inequality; the singleton forms ensure that it vanishes only at zero. If the coordinate set is empty, this is the unique norm on the zero-dimensional space. Finally, a compatible selection contains at most one coordinate of the \(i\)-block, proving (4). Linearity follows from the coordinate formula. ◻

Proof. Intersect any compatible selection with the blocks in \(\mathcal B\). Heredity preserves compatibility, and the sum is unchanged because all other blocks of \(z\) vanish. Conversely, each selection on the right of (9) is a selection in the full maximum. This proves equality.

For a pair of vertices there are at most \(2d\) distinct query blocks. First aggregate the coordinate contributions of all occurrences of each repeated query. For each distinct query \(i\), enumerate the at most \(q^{d-1}\leq r\) assignments on its scope, and keep exactly those satisfying every source constraint internal to that scope. This computes \(\Lambda_i\) and its slots. Next choose either no label or one of these labels in each block. There are at most \((1+r)^{2d}\) choices. For each choice, test agreement on repeated variables and scan the source list to test every constraint internal to the union of the chosen scopes. This union has at most \(2d(d-1)\) variables. The surviving choices are precisely the selections on the right of (9), and their absolute coordinate sums give the required maximum. Neither the labels nor the compatibility test requires satisfying any constraint outside the indicated scope union. ◻

Proof. Let \(L\) be the source bit length. The fixed integers \(m,d\) determine \(p\) and the rational number \(t\) by [src:construction-parameters]. The fixed alphabets determine \(q\) and \(r=q^{d-1}\). All these quantities are therefore computable constants independent of \(L\). Since the constraint list is explicit, \(M=O(L)\), and (8) gives \(n=O(L^{\binom d2})\). A vertex description contains a fixed number of source indices and grid entries. Thus all vertices can be enumerated and assigned identifiers of \(O(1+\log n)\) bits.

Apply 5 to each unordered pair of distinct vertices. All label and selection enumerations have a fixed number of choices. Variable comparisons, sorting, constraint scans, and projection-map evaluations take polynomial bit time in \(L\). The arithmetic of the edge test uses only rational grid entries. In fact, every coordinate of \(S_v+S_w\) has denominator \(p\), after summing all repeated-block contributions. The local maximum is therefore \(\zeta/p\) for a nonnegative integer \(\zeta\). By (4) and the triangle inequality, \(\zeta/p\leq2d\), so its numerator and denominator have bit lengths bounded solely in terms of the fixed parameters. Since \(t=\sqrt d/(4m)\) and \(\sqrt d\) is an integer, the edge test is precisely \[2m\zeta\leq p\sqrt d.\] Both sides are integers, so the test involves no approximation of a real number.

Checking all pairs and writing every qualifying edge takes \[O\bigl((1+n^2)\operatorname{poly}(L+\log n)\bigr)\] bit operations, with constants depending only on the fixed parameters and alphabets. Formula (8) also computes \(n\) by integer arithmetic with \(O(1+\log n)\) output bits. Thus the construction has polynomial bit complexity, including its explicit vertex and edge lists. It runs on every source instance with these alphabets, regardless of whether the gap promise holds. ◻

Proof. Take independent uniform \(C_1,\ldots,C_d\) on \([-1,1]\), and round each to the midpoint of its subinterval in the partition defining \(\mathcal T\). Boundary choices have probability zero. The rounded variables have the required independent laws, and \[\left|\sum_jT_j-\sum_jC_j\right|\leq\frac dp<\frac12.\] Put \(A=t+d/p=a\sqrt d+d/p\). We bound the central probability \(\Pr[|\sum_jC_j|\leq A]\).

Each \(C_j\) may be generated as \((L_j+U_j)/2\), where \(L_j\) is a fair sign and \(U_j\) is uniform on \([-1,1]\), all independent. The two sign choices give uniform distributions on the two half intervals of \([-1,1]\), so this is indeed the uniform distribution on the full interval. Conditional on \((U_1,\ldots,U_d)\), the event \(|\sum_jC_j|\leq A\) places \(\sum_jL_j\) in an interval of length \[4A=4a\sqrt d+4d/p<4a\sqrt d+2.\] The possible sign sums are spaced by two. An interval of length \(D\) contains at most \(D/2+1\) values from such a lattice, so this interval contains fewer than \(2a\sqrt d+2\) possible sign sums.

Write \(d=2d_0\). The sign-sum probabilities are \(4^{-d_0}\binom{2d_0}{v}\), for \(0\leq v\leq2d_0\). Consecutive ratios \((2d_0-v)/(v+1)\) show that the largest is the central one. It satisfies \[4^{-d_0}\binom{2d_0}{d_0} =\prod_{u=1}^{d_0}\left(1-\frac1{2u}\right) \leq\frac1{\sqrt{d_0+1}} <\frac{\sqrt2}{\sqrt d}.\] For the middle inequality, square the product and use \[\left(1-\frac1{2u}\right)^2\leq\frac{u}{u+1} \qquad(u\geq1);\] indeed the right side minus the left side is \((3u-1)/(4u^2(u+1))>0\), and the resulting product telescopes. The conditional central probability, and therefore its average, is bounded by \[\Pr\left[\left|\sum_jC_j\right|\leq A\right] <\sqrt2\left(2a+\frac2{\sqrt d}\right).\] Symmetry gives \[\Pr\left[\sum_jC_j>A\right] =\frac12\left(1- \Pr\left[\left|\sum_jC_j\right|\leq A\right]\right) >\frac12-\sqrt2\left(a+\frac1{\sqrt d}\right).\] On this event, rounding leaves \(\sum_jT_j>t\). Finally, \(\sqrt d>4m=1/a\) by [src:dimension-bounds], and hence \[\sqrt2\left(a+\frac1{\sqrt d}\right) <2\sqrt2\,a<3a=\frac3{4m}<\frac1m.\] This proves both inequalities in (10). ◻

Proof. Let \(A\) be a labeling satisfying every source constraint. Its restriction \(\lambda_{A,i}\) to \(P(i)\) belongs to \(\Lambda_i\) for every query \(i\). The selection \[I_A=\{(i,\lambda_{A,i}):i\in\mathcal Q\}\] belongs to \(\mathcal I\): the labels agree on overlaps, and every constraint internal to their scope union is satisfied by \(A\). Keep precisely the vertices for which \[ \sum_{j=1}^d s_{j,\operatorname{slot}_{i_j(\mathbf c)} (\lambda_{A,i_j(\mathbf c)})}>t. \tag{11}\] For a uniform vertex, conditional on the seed tuple, the selected slot in each weight vector is fixed. Its entries are independent uniform elements of \(\mathcal T\), one from each independent \(s_j\). Coincident endpoint questions or slot numbers do not change this independence. By 7, more than a \((1/2-1/m)\) fraction of vertices are kept.

For two distinct kept vertices \(v,w\), evaluating \(S_v+S_w\) on \(I_A\) gives exactly the sum of their two expressions in (11). This includes all contributions even when the same query appears in both vertices. The sum exceeds \(2t\), so (3) rules out the edge in (7). The kept vertices are therefore independent. Their complement is a vertex cover of size less than \((1/2+1/m)n\). ◻

Proof. Let \(\mathbf 1_I\in\mathbb R^{\mathcal P}\) be the indicator vector of \(I\). For \(\zeta\in A_*\cup(-A_*)\), \(I\in\mathcal I\), and \(\varepsilon\in\{-1,1\}\), form the finite collection of affine expressions \[ L_{\zeta,I,\varepsilon}(\boldsymbol s_J) =\varepsilon\langle\mathbf 1_I,c_0-\zeta\rangle +\varepsilon\langle v_I(\boldsymbol i),\boldsymbol s_J\rangle. \tag{37}\] For either \(\mathcal C=A_*\) or \(\mathcal C=-A_*\), \[\mathop{\mathrm{dist}}_*\left(c_0+\sum_{j\in J}z(i_j,s_j),\mathcal C\right) =\min_{\zeta\in\mathcal C} \max_{I\in\mathcal I,\,\varepsilon\in\{-1,1\}} L_{\zeta,I,\varepsilon}(\boldsymbol s_J).\] In particular, \(\psi_{\boldsymbol i}\) is continuous and piecewise affine, with finitely many pieces.

Compare all pairs of candidates in (37). If two candidates with different slope vectors in the unfrozen weights tie in value, set \(g=0\). Otherwise take the true gradient of the finite formula for \(\psi_{\boldsymbol i}\). This latter choice is well-defined. Two candidates with the same slope either never tie or are identical affine functions. All other comparisons are strict at such a point and persist in a neighborhood; each minimum and maximum there selects one affine function up to identical copies. The resulting formula is affine in that neighborhood. Fixing a deterministic order on candidates resolves any choice between identical copies without changing its gradient.

Each discarded equality has a nonzero normal in the unfrozen coordinates, hence defines a proper affine hyperplane. No choice of frozen weights changes that fact, since frozen weights change the offsets but not the slopes. Identical slopes caused by repeated endpoint questions or other coincidences are allowed. Finite comparisons prove measurability, and the rule is defined even at query tuples that cannot arise from the hidden seed law. Its formula uses the queries themselves and no additional seed information.

At a point not discarded, choose an active affine expression in each distance formula. Write their slopes as \(\varepsilon_-v_{I_-}(\boldsymbol i)\) for the distance to \(-A_*\) and \(\varepsilon_+v_{I_+}(\boldsymbol i)\) for the distance to \(A_*\). Since \(F\) is half the difference of these distances, \[g=\frac12\bigl(\varepsilon_-v_{I_-}(\boldsymbol i) -\varepsilon_+v_{I_+}(\boldsymbol i)\bigr).\] Both vectors in this average are signed compatible-incidence vectors, proving (35). At discarded points the chosen value zero also belongs to the symmetric hull. Every signed incidence vector has block \(\ell^1\) norm at most one and zero entries in the unused slots, so convexity proves (36) at every tuple. ◻

Proof. Replacing the own block \(s\) by \(s'\), with a seed configuration and other weights fixed, changes the integrand in (34) by at most \(\|s-s'\|_\infty\). The same bound holds after averaging. In particular, every scalar-coordinate difference quotient of the integrand is bounded in absolute value by one.

For each fixed hidden seed tuple, the full gradient identification in 11 holds outside a null set in all batch weights. Fubini implies that for almost every own \(s\) it holds for almost all other weight blocks. The conditional seed law \(\kappa_j(u)\) has finite support and does not depend on \(s\), so the exceptional sets may be united over its support and over the finitely many weight coordinates. At the remaining own values, the coordinate difference quotients converge almost surely to \(g_{j,t'}\). Dominated convergence gives (40); the boundary of the cube has measure zero.

Every coordinate-line restriction of \(H_j(u,\cdot)\) is Lipschitz and hence absolutely continuous. By Fubini applied to (40), for almost every fixing of the other own coordinates its derivative agrees almost everywhere with the corresponding entry of \(\bar g_j\). The fundamental theorem of calculus therefore expresses differences between any two values on such a line as the integral of that entry.

Let \(w_0\) be the restriction of \(H_j(u,\cdot)\) to one of these lines. For \(x,y\in[-1,1]\), Cauchy–Schwarz gives \[|w_0(x)-w_0(y)|^2 \leq |x-y|\int_{\min(x,y)}^{\max(x,y)}|w_0'(z)|^2\,dz \leq2\int_{-1}^1|w_0'(z)|^2\,dz.\] For independent uniform \(X,Y\in[-1,1]\), this implies \[\mathop{\mathrm{Var}}(w_0(X))=\tfrac12\mathbb E|w_0(X)-w_0(Y)|^2 \leq\int_{-1}^1|w_0'(z)|^2\,dz =2\mathbb E|w_0'(X)|^2.\] The product decomposition of Efron and Stein (Efron and Stein 1981, sec. 2) bounds variance by the sum of the averaged one-coordinate conditional variances. To see this consequence directly, decompose the identity at each scalar coordinate into its averaging projection and its orthogonal complement. The resulting orthogonal components are indexed by subsets of coordinates. Total variance counts every nonconstant squared component once, while the sum of one-coordinate conditional variances counts it once for each member of its nonempty index subset. Applying the line estimate, integrating over the other coordinates, and summing proves (41). Averaging that bound over the own tuples and summing over \(j\), then using (33), proves (42). ◻

Proof. The mean block bound gives \[\frac\beta2|\mathcal L_j(u,s)|\leq\|\bar g_j(u,s)\|_1\leq1, \qquad |\mathcal L_j(u,s)|\leq2/\beta=\ell.\] It also gives zero dummy entries, so thresholding returns only valid labels. Finite threshold comparisons of measurable functions, with an empty-list fallback, prove totality and measurability.

We first transfer the retained mass of the own conditional means to the full gradient rule \(g\), and then apply its pointwise hull bound. For an actual own input, let \(T_j\subset[r]\) be the set of slots of \(L_j\), and write \(\mathcal G_j\) for the information \((u_j,s_j)\). The conditional mean in (38) is a version of \(\mathbb E[g_j\mid\mathcal G_j]\), defined by the displayed kernel even at own values of probability zero. For slots outside \(T_j\), (39) and the threshold give \[\sum_{t'\notin T_j}|\bar g_{j,t'}|^2 \leq\frac\beta2\sum_{t'\notin T_j}|\bar g_{j,t'}| \leq\frac\beta2.\] For the list slots, each mean entry has magnitude at most one, and conditional Jensen gives \[\sum_{t'\in T_j}|\bar g_{j,t'}|^2 \leq\sum_{t'\in T_j}|\bar g_{j,t'}| \leq\mathbb E\left[\sum_{t'\in T_j}|g_{j,t'}| \,\middle|\,\mathcal G_j\right].\] The last inequality uses the fact that \(T_j\) is determined by \(\mathcal G_j\). Taking expectations, summing, and applying (42) therefore yields \[ \mathbb E\sum_{j\in J}\sum_{\lambda\in L_j} |g_{j,\operatorname{slot}_{i_j}(\lambda)}| \geq\beta h-\frac\beta2h=\frac{\beta h}{2}. \tag{46}\]

For arbitrary fixed queries and arbitrary lists of valid labels, the sum of absolute values over their slot sets is a convex function of the full vector in \(\mathbb R^{J\times[r]}\). On a signed generator \(\pm v_I(\boldsymbol i)\) it equals the number of positions hit by that selection \(I\), since each block contains at most one selected slot. Its value on every point of the hull in (35) is consequently at most the maximum such hit count. At every realized tuple, apply this deterministic statement to the realized lists and the full vector \(g\): \[ \sum_{j\in J}\sum_{\lambda\in L_j} |g_{j,\operatorname{slot}_{i_j}(\lambda)}|\leq Z. \tag{47}\] No independence between the lists and the gradient, or between positions, is required. Combining (46) and (47) proves (45), with \(\beta h/2=2\) from (31).

Finally, (34) and (38) integrate over hidden seeds against the fixed law \(\kappa_j(u)\), and over other weights against their fixed cube laws. Their actual realized values are not inputs to the resulting mean function. Thus (43) has exactly the stated own-input dependence. No efficiency of this rule is needed for the soundness argument. ◻