Answer: The promised vector-SEBB allocation problem is NP-hard. For the prescribed pilot/production protocol and reported radius, the necessary and sufficient worst-case query budget up to universal constants is $\Theta(K+qH^2/\varepsilon^2+\sqrt{qc}\,J^{3/2}/\varepsilon)$, with $q,c,H,J$ defined above.
Theorem 6.1 — class: algorithmic
Given \(\tau\) types with rational masses \(\mu\), a differentiable coalition-value function \(F\) with \(F(0)=0\), a gradient oracle on the path \(\lambda\mu\), a partition of \([0,1]\) with known coordinate range bounds, and a query budget \(B\), estimate \(\Phi_t=\int_0^1 \partial_t F(\lambda\mu)\,d\lambda\) for every type. Using iid samples of \(\lambda\) within the path intervals, find an allocation of the \(B\) queries that minimizes a valid vector-SEBB confidence radius, and return the estimate, radius, and aggregate allocations \(\mu_t\hat\Phi_t\); characterize the query budget needed to reach a specified radius.
A society is specified by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; the number of gradient coordinates is \(m=\tau\).
Let \(F\) be continuously differentiable on a neighborhood of \([0,\mu]\), with \(F(0)=0\); values and derivatives may have either sign. A gradient query at \(\lambda\mu\) returns all coordinates of \(g(\lambda)=\nabla F(\lambda\mu)\). Define \(\Phi_t=\int_0^1g_t(\lambda)\,d\lambda\).
Input includes a rational partition \(0=a_0<\cdots<a_K=1\), weights \(w_i=a_i-a_{i-1}\), rational bounds \(\ell_{it}\le g_t(\lambda)\le u_{it}\) on interval \(i\), widths \(D_{it}=u_{it}-\ell_{it}\ge0\), confidence parameter \(\delta\in(0,1)\), and integer budget \(B\ge4K\).
Each query samples \(\lambda\) uniformly within its chosen interval, independently of other draws. Spend \(2K\) queries on two pilot draws per interval and let \(v_{it}\) be their unbiased coordinate sample variances. Choose integer production counts \(n_i\ge2\) with \(\sum_i n_i=B-2K\), using the pilot data; production draws are independent of the pilot.
For any nonnegative variance table \(s\), put \(p=\delta/\tau\), \(\alpha_t=\frac4{17}\sum_iw_i^2D_{it}^2/n_i\), \(\beta_t=\log(3/p)\max_i(w_i^2D_{it}^2/n_i^2)\), and \(\gamma_t=2\sum_iw_i^2(n_i-1)s_{it}/n_i^2+\log(6K/p)\sum_iw_i^2D_{it}^2/n_i^2+\beta_t\).
Define the vector-SEBB radius by \(R(n,s)^2=\log(6/p)\sum_t[\alpha_t+(\sqrt{\beta_t}+\sqrt{\gamma_t})^2]\). Allocation means global minimization of the planning criterion \(R(n,v)\), holding the pilot variances fixed.
From production samples, form interval means \(\bar g_i\), unbiased variances \(s_{it}\), estimates \(\hat\Phi_t=\sum_iw_i\bar g_{it}\), and aggregate allocations \(\mu_t\hat\Phi_t\); the reported radius must satisfy \(\Pr(\|\hat\Phi-\Phi\|_2\le R(n,s))\ge1-\delta\).
Use an ideal sampling and gradient-oracle model, counting queries separately from arithmetic. For numerical allocation, input rational \(r\ge0\) and \(\eta>0\), with the promise that the minimum planning radius is at most \(r\) or at least \(r+\eta\); \(L\) is the total bit length of the rational inputs and supplied pilot statistics. State running times in \(m,\tau,K,B,L\), and \(\log(1/\eta)\).
Is this promised vector-SEBB allocation problem solvable in polynomial time, or is it NP-hard?
What query budget is necessary and sufficient, in the worst case over admissible \(F\), to obtain a reported radius at most a specified \(\varepsilon>0\) with probability at least \(1-\delta\)?
For finite vector-valued strata, a vector-SEBB concentration bound is known; the accompanying sequential method minimizes a one-step forecast with variances held fixed, without establishing global allocation optimality. [Burgess and Chapman](https://www.ijcai.org/proceedings/2021/0011.pdf)
No result settling this specific continuous allocation problem was verified.
The promised numerical allocation problem is NP-hard, even when every pilot variance is zero and $B$ is linear in $K$.
For the prescribed reported radius $R(n,s)$, the necessary and sufficient worst-case query budget, up to universal multiplicative constants, is
$$
\Theta\left(
K+
\frac{qH^2}{\varepsilon^2}
+
\frac{\sqrt{qc}\,J^{3/2}}{\varepsilon}
\right),
$$
where
$$
q=\log\frac{6\tau}{\delta},
\qquad
c=\log\frac{6K\tau}{\delta},
\qquad
d_i=w_i\sqrt{\sum_{t=1}^{\tau}D_{it}^2},
$$
and
$$
H=\sum_{i=1}^K d_i,
\qquad
J=\sum_{i=1}^K d_i^{2/3}.
$$
Explicit necessary and sufficient finite-budget inequalities are proved below. The sufficient inequality makes $R(n,s)\le\varepsilon$ for every production outcome consistent with the stated bounds.
All logarithms are natural. We assume the bounds admit at least one admissible $F$. If every width is zero, the radius is identically zero, and the prescribed protocol requires exactly $4K$ queries.
Let $\mathcal P$ denote all pilot data. Conditional on $\mathcal P$, the chosen counts $n_i$ are fixed, and the production draws remain independent uniform draws within their respective intervals.
For coordinate $t$, the mean in interval $i$ is
$$
\theta_{it}
=
\frac{1}{w_i}
\int_{a_{i-1}}^{a_i}g_t(\lambda)\,d\lambda.
$$
Consequently,
$$
\mathbb E[\hat\Phi_t\mid\mathcal P]
=
\sum_iw_i\theta_{it}
=
\Phi_t.
$$
We now justify applying the finite-stratum bound to these continuous distributions. The finite vector-SEBB theorem, with sampling with replacement, positive weights $w_i$, coordinate widths $D_{it}$, unbiased sample variances, and coordinate failure parameter $p=\delta/\tau$, gives the radius in the question: the replacement factors are both $1/n_i$. See the multidimensional extension in [Burgess and Chapman](https://www.ijcai.org/proceedings/2021/0011.pdf).
Fix the pilot data and hence the counts. For each positive integer $M$, replace the uniform distribution in interval $i$ by the uniform distribution on its $M$ midpoint values of $g$. Couple a continuous production draw $\lambda$ with the midpoint of the cell containing it.
Because $F$ is continuously differentiable, $g$ is continuous and therefore uniformly continuous on $[0,1]$. For the finitely many production draws, this coupling gives almost-sure convergence of:
Every finite approximation obeys the original coordinate bounds, and sampling remains independent across draws. The finite theorem therefore applies to each approximation.
Write $E_M$ for the norm of the approximation’s estimation error and $R_M$ for its radius. Their almost-sure limits are $E$ and $R$. If $E>R$, then eventually $E_M>R_M$, so
$$
\mathbf 1_{\{E>R\}}
\le
\liminf_{M\to\infty}\mathbf 1_{\{E_M>R_M\}}.
$$
Fatou’s lemma gives
$$
\Pr(E>R\mid\mathcal P)
\le
\liminf_{M\to\infty}\Pr(E_M>R_M\mid\mathcal P)
\le\delta.
$$
Averaging over the pilot data proves
$$
\Pr\!\left(\|\hat\Phi-\Phi\|_2\le R(n,s)\right)\ge1-\delta.
$$
This argument permits arbitrary dependence among coordinates of a sampled vector. It also permits either sign of the gradient values.
The aggregate allocations have the expected target:
$$
\sum_t\mu_t\Phi_t
=
\int_0^1\nabla F(\lambda\mu)\cdot\mu\,d\lambda
=
F(\mu).
$$
Moreover, on the confidence event,
$$
\left\|
(\mu_t\hat\Phi_t)_t-(\mu_t\Phi_t)_t
\right\|_2
\le
\left(\max_t\mu_t\right)R(n,s).
$$
We reduce from CLIQUE on regular simple graphs. This problem is NP-complete; the restriction follows, for example, by complementing cubic instances of INDEPENDENT SET. The regular-graph statement is recorded as Proposition 17 of [Fomin, Golovach, Strømme, and Thilikos](https://link.springer.com/article/10.1007/s00453-020-00677-8).
Let $G$ be a $d$-regular graph on $K$ vertices, with edge set $E$, and let the requested clique size satisfy $2\le k\le K$. Discarding the trivial cases preserves NP-hardness.
Create one stratum per vertex, with
$$
a_i=\frac{i}{K},
\qquad
w_i=\frac1K.
$$
Set
$$
B=4K+k,
\qquad
\delta=\frac12,
\qquad
M=10K.
$$
Use one coordinate per edge and one additional coordinate per vertex. Pad with zero-width coordinates until the coordinate count $\tau$ is a power of two. Thus
$$
m=\tau,
\qquad
K+|E|\le\tau<2(K+|E|)\le2K^2.
$$
Assign every supported type mass $1/\tau$. These masses are positive dyadic rationals and sum to one.
All lower bounds are zero. Choose the upper bounds as follows:
Supply pilot variances $v_{it}=0$. These statistics are realizable: the admissible function $F\equiv0$ produces them deterministically. The bounds need not be tight.
For this construction, put
$$
a=\frac4{17},
\qquad
q=\log(12\tau),
\qquad
b=\log(6\tau),
\qquad
c=\log(12K\tau).
$$
We minimize the normalized squared objective
$$
\mathcal J(n)=\frac{R(n,0)^2}{q}.
$$
A coordinate supported only in stratum $i$, with $w_iD_{it}=M$, contributes
$$
M^2f(n_i)
$$
to $\mathcal J$, where
$$
f(x)=\frac ax+\frac h{x^2},
\qquad
h=\left(\sqrt b+\sqrt{c+b}\right)^2.
$$
Since
$$
f''(x)=\frac{2a}{x^3}+\frac{6h}{x^4}>0,
$$
its consecutive decrements decrease as $x$ increases. In particular,
$$
f(2)-2f(3)+f(4)
=
\frac a{12}+\frac{13h}{144}
\ge
\frac{13c}{144}.
$$
An edge coordinate with endpoint counts $x,y$ contributes
$$
e(x,y)
=
a\left(\frac1x+\frac1y\right)
+
\left(
\frac{\sqrt b}{\min(x,y)}
+
\sqrt{
c\left(\frac1{x^2}+\frac1{y^2}\right)
+
\frac b{\min(x,y)^2}
}
\right)^2.
$$
This expression decreases in either count. For $x,y\ge2$,
$$
0\le e(x,y)\le e(2,2)
\le a+c+b
\le3c.
$$
The production budget is
$$
\sum_i n_i=B-2K=2K+k.
$$
If some count $n_u\ge4$, another count must equal two: otherwise the total would exceed $3K$, whereas $2K+k\le3K$.
Transfer one sample from such a stratum $u$ to a stratum $v$ with count two. The additional-coordinate contribution decreases by at least
$$
M^2\frac{13c}{144}.
$$
The total edge-coordinate contribution can increase by at most
$$
|E|\,e(2,2)\le\frac32K^2c.
$$
But
$$
M^2\frac{13c}{144}
=
\frac{325}{36}K^2c
>
\frac32K^2c.
$$
The transfer strictly decreases the objective.
Therefore every global minimizer satisfies
$$
n_i\in\{2,3\},
$$
with exactly $k$ strata receiving three samples.
Write
$$
e_{22}=e(2,2),
\qquad
e_{23}=e(2,3),
\qquad
e_{33}=e(3,3).
$$
Direct substitution gives
$$
e_{22}
=
a+\frac{\left(\sqrt b+\sqrt{2c+b}\right)^2}{4},
$$
$$
e_{33}
=
\frac{2a}{3}
+\frac{\left(\sqrt b+\sqrt{2c+b}\right)^2}{9},
$$
and
$$
e_{23}
=
\frac{5a}{6}
+\frac{\left(3\sqrt b+\sqrt{13c+9b}\right)^2}{36}.
$$
Define the interaction coefficient
$$
\lambda=e_{22}-2e_{23}+e_{33}.
$$
Expanding the preceding expressions yields
$$
\lambda
=
\frac{\sqrt b}{18}
\left(
13\sqrt{2c+b}
-
6\sqrt{13c+9b}
-
5\sqrt b
\right).
$$
Both quantities in the following comparison are positive, and
$$
36(13c+9b)-169(2c+b)=130c+155b>0.
$$
Hence
$$
6\sqrt{13c+9b}>13\sqrt{2c+b},
$$
which proves
$$
\lambda<-\frac{5b}{18}<0.
$$
Let $S$ be the $k$ vertices whose strata receive three samples, and let $e_G(S)$ be the number of edges induced by $S$. Regularity gives exactly
$$
dk-2e_G(S)
$$
edges with one endpoint in $S$, and
$$
|E|-dk+e_G(S)
$$
edges with neither endpoint in $S$.
The additional-coordinate contribution is independent of $S$. Therefore
$$
\mathcal J(n)=T_0+\lambda e_G(S),
$$
where
$$
T_0
=
M^2\bigl((K-k)f(2)+kf(3)\bigr)
+
|E|e_{22}
+
dk(e_{23}-e_{22}).
$$
Since $\lambda<0$, global minimization maximizes $e_G(S)$.
Let
$$
C_k=\binom{k}{2},
\qquad
Z=q(T_0+\lambda C_k),
\qquad
\kappa=-\lambda.
$$
If $G$ has a $k$-clique, then
$$
\min_n R(n,0)^2=Z.
$$
If it has no $k$-clique, then every $k$-vertex set has at most $C_k-1$ edges, so
$$
\min_n R(n,0)^2\ge Z+q\kappa.
$$
We verify positivity and polynomial bounds before taking square roots.
Because every $e_{xy}$ above is at most $3c$,
$$
|\lambda|\le12c.
$$
Also $f(3)\ge c/9$. Consequently,
$$
\frac Zq
\ge
\frac{100}{9}K^3c-9K^2c
>0.
$$
For every feasible count vector,
$$
f(n_i)\le f(2)\le2c.
$$
Using the edge bound,
$$
R(n,0)^2
\le
202qcK^3.
$$
Our choice of $\tau$ implies
$$
q\le c\le\log(24K^3)\le4K
\qquad(K\ge2).
$$
Thus every feasible radius is at most
$$
U=100K^3.
$$
Moreover,
$$
q\kappa>\frac{5qb}{18}>\frac14.
$$
Writing $\rho=\min_nR(n,0)$, a no-instance therefore satisfies
$$
\rho-\sqrt Z
=
\frac{\rho^2-Z}{\rho+\sqrt Z}
\ge
\frac{q\kappa}{2U}
>
\frac1{8U}.
$$
Set
$$
G_0=\frac1{8U}.
$$
Compute a rational $r$ satisfying
$$
\sqrt Z\le r\le\sqrt Z+\frac{G_0}{4},
$$
and set
$$
\eta=\frac{G_0}{2}.
$$
Then:
Certified evaluation of the displayed logarithms and square roots constructs $r$ in polynomial time. Their arguments and the radius are polynomially bounded in $K$, and the required precision is only $O(\log K)$ bits beyond the integer part. In particular,
$$
\frac1\eta=1600K^3.
$$
The constructed input has
$$
m=\tau=O(K^2),
\qquad
B=O(K),
\qquad
L=\operatorname{poly}(K),
\qquad
\log(1/\eta)=O(\log K).
$$
This proves NP-hardness of the promised numerical problem. Unless $\mathrm P=\mathrm{NP}$, it has no algorithm polynomial in all the parameters requested in the question.
For any feasible count vector, define
$$
A(n)=\sum_i\frac{d_i^2}{n_i},
\qquad
C(n)=\sum_i\frac{d_i^2}{n_i^2},
\qquad
N=\sum_i n_i=B-2K.
$$
For every nonnegative variance table $s$, the radius satisfies
$$
R(n,s)^2
\ge
q\left(\frac4{17}A(n)+cC(n)\right).
$$
Indeed, summing the $\alpha_t$ terms gives $(4/17)A(n)$, and summing just the width-sum terms in $\gamma_t$ gives $cC(n)$. All remaining terms are nonnegative.
Cauchy–Schwarz gives
$$
H^2
=
\left(
\sum_i\frac{d_i}{\sqrt{n_i}}\sqrt{n_i}
\right)^2
\le A(n)N.
$$
Hölder’s inequality, with exponents $3$ and $3/2$, gives
$$
J
=
\sum_i
\left(\frac{d_i^2}{n_i^2}\right)^{1/3}
n_i^{2/3}
\le C(n)^{1/3}N^{2/3}.
$$
Hence
$$
A(n)\ge\frac{H^2}{N},
\qquad
C(n)\ge\frac{J^3}{N^2}.
$$
It follows that every reported radius obeys the deterministic inequality
$$
R(n,s)^2
\ge
\frac{4qH^2}{17N}
+
\frac{qcJ^3}{N^2}.
$$
Thus even positive probability of reporting a radius at most $\varepsilon$ requires
$$
\frac{4qH^2}{17(B-2K)}
+
\frac{qcJ^3}{(B-2K)^2}
\le\varepsilon^2.
$$
In particular, the following conditions are necessary:
$$
B\ge4K,
$$
$$
B-2K\ge\frac{4qH^2}{17\varepsilon^2},
$$
and
$$
B-2K\ge
\frac{\sqrt{qc}\,J^{3/2}}{\varepsilon}.
$$
These lower bounds hold for every admissible $F$, every pilot outcome, and every production outcome.
For $n$ observations in an interval of width $D$, their biased empirical variance is at most $D^2/4$. To verify this, let $\bar x$ be their mean. The inequality
$$
(x-\ell)(u-x)\ge0
$$
implies
$$
\frac1n\sum_jx_j^2-\bar x^2
\le
(\bar x-\ell)(u-\bar x)
\le\frac{D^2}{4}.
$$
Therefore their unbiased variance satisfies
$$
s\le\frac{n}{n-1}\frac{D^2}{4}.
$$
For the two pilot observations, the unbiased variance is
$$
v=\frac{(x_1-x_2)^2}{2}\le\frac{D^2}{2}.
$$
Let
$$
A_t(n)=\sum_i\frac{w_i^2D_{it}^2}{n_i},
\qquad
C_t(n)=\sum_i\frac{w_i^2D_{it}^2}{n_i^2},
$$
and put
$$
b=\log\frac{3\tau}{\delta}.
$$
Since $b\le c$, the pilot bounds imply
$$
\gamma_t(n,v)
\le A_t(n)+cC_t(n)+\beta_t(n),
$$
and
$$
\beta_t(n)\le bC_t(n).
$$
Using $(\sqrt x+\sqrt y)^2\le2x+2y$, we obtain
$$
R(n,v)^2
\le
q\left(\frac{38}{17}A(n)+6cC(n)\right).
$$
The production variance bound gives
$$
2\sum_iw_i^2\frac{(n_i-1)s_{it}}{n_i^2}
\le\frac12A_t(n).
$$
Because the pilot variances are nonnegative,
$$
\gamma_t(n,s)\le\gamma_t(n,v)+\frac12A_t(n).
$$
For fixed $\beta\ge0$, define
$$
h_\beta(x)=(\sqrt\beta+\sqrt x)^2.
$$
On $x\ge\beta$, increasing $x$ by $z\ge0$ increases $h_\beta(x)$ by at most $2z$: for positive $x$, its derivative is
$$
1+\sqrt{\beta/x}\le2,
$$
and the case $\beta=0$ is immediate.
Both planning and production $\gamma_t$ contain $\beta_t$. It follows that
$$
R(n,s)^2\le R(n,v)^2+qA(n).
$$
Since
$$
R(n,v)^2\ge\frac{4q}{17}A(n),
$$
we conclude
$$
R(n,s)^2\le\frac{21}{4}R(n,v)^2.
$$
This comparison is deterministic and holds for every feasible count vector.
Assume $H>0$; otherwise all widths are zero. Define benchmark counts
$$
n_i^{(0)}
=
2+
\left\lceil
\frac{24qHd_i}{\varepsilon^2}
+
\frac{8\sqrt{qc}\,J^{1/2}d_i^{2/3}}{\varepsilon}
\right\rceil.
$$
They satisfy
$$
\sum_i n_i^{(0)}
\le
3K+
\frac{24qH^2}{\varepsilon^2}
+
\frac{8\sqrt{qc}\,J^{3/2}}{\varepsilon}.
$$
Suppose the total budget obeys
$$
B\ge
\left\lceil
5K+
\frac{24qH^2}{\varepsilon^2}
+
\frac{8\sqrt{qc}\,J^{3/2}}{\varepsilon}
\right\rceil.
$$
The benchmark counts fit within the production budget $B-2K$. Add any unused production samples to obtain a feasible vector $\tilde n$.
For strata with $d_i>0$, the defining lower bounds on $\tilde n_i$ imply
$$
A(\tilde n)\le\frac{\varepsilon^2}{24q}
$$
and
$$
C(\tilde n)\le\frac{\varepsilon^2}{64qc}.
$$
Zero-width strata contribute zero to both sums.
Let $n^\star$ be any global minimizer of the pilot planning criterion. Its defining optimality gives
$$
R(n^\star,v)^2
\le
R(\tilde n,v)^2.
$$
Applying the preceding inequalities,
$$
\begin{aligned}
R(n^\star,s)^2
&\le
\frac{21}{4}R(n^\star,v)^2\\
&\le
\frac{21}{4}q
\left(
\frac{38}{17}A(\tilde n)+6cC(\tilde n)
\right)\\
&\le
\frac{21}{4}
\left(
\frac{38}{17\cdot24}+\frac6{64}
\right)\varepsilon^2\\
&=
\frac{2135}{2176}\varepsilon^2
<
\varepsilon^2.
\end{aligned}
$$
Therefore the displayed budget is sufficient for every admissible $F$ and every sample outcome. Combining this deterministic radius bound with Section 1 gives
$$
\Pr\!\left(
\|\hat\Phi-\Phi\|_2\le R(n^\star,s)\le\varepsilon
\right)\ge1-\delta.
$$
The lower and upper bounds prove the query order stated at the beginning. Global optimality is used here to compare against the benchmark allocation; finding that optimizer remains NP-hard.
For example, if $w_i=1/K$ and $D_{it}=D$ for every stratum and coordinate, then
$$
H=\sqrt{\tau}\,D,
\qquad
J^{3/2}=\sqrt{K\tau}\,D,
$$
and the query order becomes
$$
\Theta\left(
K+
\frac{q\tau D^2}{\varepsilon^2}
+
\frac{D\sqrt{qcK\tau}}{\varepsilon}
\right).
$$
The widths are essential parameters: unrestricted widths preclude a uniform budget depending only on $\tau,K,\delta,\varepsilon$.
The protocol uses exactly $B$ gradient queries. Reading the returned vectors and maintaining pilot and production statistics takes $O(mB)$ ideal arithmetic operations. Computing the estimates and aggregate allocations takes another $O(mK)$ operations.
For the supplied rational planning data, a fixed count vector’s radius can be evaluated to absolute error at most $\eta/8$ in
$$
O(mK)\,
\operatorname{poly}\left(
L+\log B+\log(mK+1)+\log^+(1/\eta)
\right)
$$
bit operations, where
$$
\log^+(x)=\max\{0,\log x\}.
$$
The coordinate maxima involve rational quantities and can be compared exactly. The logarithms and square roots admit certified rational approximations in polynomial time. Their arguments, intermediate magnitudes, and required absolute precision have bit bounds polynomial in the displayed parameters.
There are exactly
$$
C_B
=
\binom{B-3K-1}{K-1}
$$
feasible production count vectors: subtracting two from every count leaves $B-4K$ samples to distribute among $K$ strata.
Enumerating these vectors and evaluating each radius to error $\eta/8$ solves the promised decision problem. If $\tilde\rho$ is the smallest evaluated radius, compare it with $r+\eta/2$. In the lower alternative,
$$
\tilde\rho\le r+\eta/8;
$$
in the upper alternative,
$$
\tilde\rho\ge r+7\eta/8.
$$
Thus the comparison is correct.
The resulting allocation decision time is
$$
C_B\,O(mK)\,
\operatorname{poly}\left(
L+\log B+\log(mK+1)+\log^+(1/\eta)
\right).
$$
The same enumeration produces an additively accurate minimizer. The NP-hardness reduction rules out a general polynomial running time in $m,\tau,K,B,L,\log^+(1/\eta)$ unless $\mathrm P=\mathrm{NP}$.
⟨structured verdict parsed — rendered above⟩
The argument resolves the assigned problem: the promised numerical allocation problem is NP-hard, and the prescribed reported radius has the claimed necessary and sufficient worst-case query order, up to universal constants. I found no major or minor issues requiring repair.
Conditional on the pilot data, the production counts are fixed and production samples remain independent. Thus the stated conditional expectation is correct:
$$
\mathbb E[\hat\Phi_t\mid\mathcal P]=\Phi_t.
$$
The cited finite result has the required coordinate formulas and failure probability $\tau p$. Specifically, Theorem 6.1 uses the replacement factors $\Omega=\Psi=1/n_i$, which yield precisely the $\alpha_t,\beta_t,\gamma_t$ in the task after substituting unbiased production variances. Positive stratum weights, bounded coordinates, and independent sampling satisfy its hypotheses. Coordinate independence is unnecessary. These formulas can be checked in [Burgess and Chapman, Theorem 6.1](https://www.ijcai.org/proceedings/2021/0011.pdf).
The midpoint approximation preserves coordinate bounds and independence. Continuity of $g$ on the compact interval gives uniform continuity, so the sampled vectors, statistics, targets, and radii converge under the proposed coupling.
The use of the strict failure event is appropriate: if $E>R$, convergence implies $E_M>R_M$ eventually. Therefore the indicator inequality and the application of Fatou’s lemma have the correct direction. Averaging the conditional bound gives the requested unconditional confidence guarantee.
The chain-rule calculation establishing
$$
\sum_t\mu_t\Phi_t=F(\mu)
$$
correctly uses $F(0)=0$. The aggregate-vector error bound follows from the operator norm of the diagonal matrix with entries $\mu_t$.
CLIQUE on regular simple graphs is NP-complete, as stated in [Fomin et al., Proposition 17](https://link.springer.com/article/10.1007/s00453-020-00677-8). Restricting to $2\le k\le K$ removes only polynomially decidable cases.
The partition, bounds, budget, masses, and supplied variances satisfy the task’s requirements. In particular:
$$
B=4K+k\ge4K,
\qquad
m=\tau,
\qquad
\mu_t=\frac1\tau.
$$
Padding to a power of two makes the masses dyadic. The zero pilot variances are realizable by the admissible function $F\equiv0$. Tight bounds are not required, so this realization does not invalidate the reduction.
Substitution into the objective gives the displayed single-stratum contribution $M^2f(n_i)$. Both the derivative calculation and the discrete decrement calculation are correct:
$$
f''(x)>0,
\qquad
f(2)-2f(3)+f(4)
=
\frac a{12}+\frac{13h}{144}
\ge\frac{13c}{144}.
$$
The edge contribution $e(x,y)$ is correctly derived and decreases in each count. The uniform upper bound
$$
e(x,y)\le e(2,2)\le a+c+b\le3c
$$
is valid in the stated range.
If a count is at least four, the budget forces another count to equal two. Convexity gives the claimed minimum decrease in the additional-coordinate contribution when transferring a sample between these strata. The bound on the possible increase of all edge contributions is conservative but valid. With $M=10K$, the decrease strictly dominates that increase.
Consequently, every global minimizer has exactly $k$ counts equal to three and all other counts equal to two.
The expressions for $e_{22},e_{23},e_{33}$ agree with direct substitution. Expanding them gives the stated interaction coefficient:
$$
\lambda
=
\frac{\sqrt b}{18}
\left(
13\sqrt{2c+b}
-
6\sqrt{13c+9b}
-
5\sqrt b
\right).
$$
The comparison of squared positive quantities is correct:
$$
36(13c+9b)-169(2c+b)=130c+155b>0.
$$
It establishes $\lambda<-5b/18<0$.
Regularity gives the stated numbers of edges with zero, one, and two endpoints in $S$. Substitution therefore yields
$$
\mathcal J(n)=T_0+\lambda e_G(S).
$$
Since $\lambda<0$, minimizing this expression maximizes the number of induced edges. The distinction between a clique and a nonclique produces the claimed squared-radius gap.
The lower bound establishing $Z>0$ is valid. The negative terms in its expression are bounded sufficiently conservatively by the stated estimates.
The upper bound
$$
R(n,0)^2\le202qcK^3
$$
and the subsequent universal radius bound $U=100K^3$ are valid for $K\ge2$. Since $Z$ is at most the actual optimum squared radius, $\sqrt Z$ also lies below this bound.
Hence the denominator in
$$
\rho-\sqrt Z
=
\frac{\rho^2-Z}{\rho+\sqrt Z}
$$
is at most $2U$. The asserted gap follows from $q\kappa>1/4$.
The chosen one-sided approximation to $\sqrt Z$ and
$$
\eta=\frac1{16U}
$$
correctly place every constructed instance into one of the two promised alternatives. In particular,
$$
\frac1\eta=1600K^3.
$$
Computing certified approximations to the logarithms and square roots requires only polynomial precision and time. Thus the reduction proves hardness even when $B$ is linear in $K$, rather than relying on a large binary-encoded budget.
Dropping nonnegative terms gives
$$
R(n,s)^2\ge q\left(\frac4{17}A(n)+cC(n)\right).
$$
The applications of Cauchy–Schwarz and Hölder use the correct factors and exponents, yielding
$$
A(n)\ge\frac{H^2}{N},
\qquad
C(n)\ge\frac{J^3}{N^2}.
$$
Therefore the displayed necessary inequality holds for every feasible count vector and every nonnegative variance table. Its necessity does not depend on constructing an adversarial function or a particular sampling outcome.
The empirical variance bounds are correct for arbitrary signed observations within the supplied intervals. They imply the stated planning-radius upper bound:
$$
R(n,v)^2
\le
q\left(\frac{38}{17}A(n)+6cC(n)\right).
$$
The production-to-planning comparison is also valid. Both relevant $\gamma_t$ values are at least $\beta_t$, and the derivative bound for $h_\beta$ applies throughout the required domain. This gives
$$
R(n,s)^2
\le R(n,v)^2+qA(n)
\le\frac{21}{4}R(n,v)^2.
$$
The benchmark counts fit the stated sufficient budget. Their lower bounds give exactly
$$
A(\tilde n)\le\frac{\varepsilon^2}{24q},
\qquad
C(\tilde n)\le\frac{\varepsilon^2}{64qc}.
$$
Zero-width strata contribute nothing to these sums.
Global optimality is used in the correct place, to compare the planning objective at $n^\star$ against the benchmark. The final constant is correct:
$$
\frac{21}{4}
\left(
\frac{38}{17\cdot24}+\frac6{64}
\right)
=
\frac{2135}{2176}<1.
$$
Thus the sufficient budget guarantees the radius threshold for every outcome. Combining this with the confidence argument gives the claimed joint event.
The necessary bounds control each of the three terms in the claimed query order, while the sufficient bound controls their sum with universal constants. This establishes the stated $\Theta$ result.
If every width is zero, every production coordinate is constant within its stratum, the estimate is exact, and the radius vanishes. The protocol still requires $4K$ queries. The assumption that at least one admissible $F$ exists appropriately excludes an empty worst-case class.
The equal-width example evaluates $H$ and $J^{3/2}$ correctly.
The number of feasible count vectors is correctly obtained by distributing $B-4K$ nonnegative excess samples:
$$
C_B=\binom{B-3K-1}{K-1}.
$$
This formula also covers $K=1$ and $B=4K$.
The fixed-vector evaluation bound and enumeration procedure solve the promised decision problem. The evaluation error margins justify comparison with $r+\eta/2$. Enumeration yields an additive approximation to a minimizing allocation, as claimed; the write-up does not assert that finite-precision evaluation identifies an exact optimizer.
Query costs and arithmetic costs are distinguished correctly. The hardness conclusion concerns global planning allocation and does not confuse it with the cited sequential one-step method.
No repair feedback is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.