Answer: —
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateChoosing closest sources is always optimal in the single learner case.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a learner, source-distance types \(D\), distribution \(\mu\), intensity \(\rho\), Markov parameters \(M\), prior \(\theta\), and budget \(\kappa\), choose \(x_d\) with \(0\le x_d\le\mu_d\) and \(\sum_d x_d\le\kappa\) to maximize \(B_\rho(0)-B_\rho(x)\), where source messages are Poisson counts of intensity \(\rho\mu_d\) and corruption changes \(q_{d,1}\) to \(q_{d,0}\).
A society is given by its support: the list of the \(\tau\) source-distance types \(d\in D\) with positive masses \(\mu_d\), each a binary rational, with \(\sum_{d\in D}\mu_d=1\). Here \(\tau\) is the support size, not the number of possible types; distances are positive integers encoded in unary, and \(m=\max D\).
There is one learner. Inputs also include binary rationals \(\rho>0\), \(\theta\in(0,1)\), \(\kappa\in[0,1]\), \(p\in[0,1]\), and mutation rates \(a,b\in[0,1/2)\) with \(a+b>0\). Let \(L\) be the total input bit length.
On states \((0,1,\varnothing)\), the column-stochastic transition matrix is \(M=\begin{pmatrix}p(1-a)&pb&0\\pa&p(1-b)&0\\1-p&1-p&1\end{pmatrix}\); define \(q_{d,j}(i)=(M^d)_{ij}\).
The true state is \(1\). An attack chooses real masses \(0\le x_d\le\mu_d\) with \(\sum_d x_d\le\kappa\), changing the initial message of corrupted mass from \(1\) to \(0\) at unit cost per unit mass.
Independently for each type, honest and corrupted source-message counts are Poisson with means \(\rho(\mu_d-x_d)\) and \(\rho x_d\); every message then follows an independent chain of length \(d\).
The learner observes distance-labelled counts \(N_{d,i}\) for \(i\in\{0,1\}\), but does not know which messages were corrupted and assumes all sources report the world state truthfully. Under an attack, these counts are independent with \(N_{d,i}\sim\operatorname{Pois}(\rho[(\mu_d-x_d)q_{d,1}(i)+x_dq_{d,0}(i)])\).
For attainable count vectors \(n\), put \(H_j(n)=\prod_{d\in D}\prod_{i\in\{0,1\}}q_{d,j}(i)^{n_{d,i}}\), using \(0^0=1\), and define the learner's posterior \(b(n)=\theta H_1(n)/(\theta H_1(n)+(1-\theta)H_0(n))\). Null messages carry no information because their probability is state-independent.
Define \(B_\rho(x)=\mathbb E_x[b(N)]\). The objective is to maximize \(B_\rho(0)-B_\rho(x)\).
Is deciding, for an additional binary-rational threshold \(t\in[0,1]\), whether some feasible \(x\) satisfies \(B_\rho(0)-B_\rho(x)\ge t\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\), with the encoding lengths of \(\rho,\kappa,t\) included in \(L\).
For finitely many sources and one learner, corrupting the closest sources is optimal, giving a polynomial-time selection algorithm without evaluating expected posteriors ([verified result](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p2234.pdf)).
No result settling this precise Poisson mass problem was located in the search.
I do not settle whether the unrestricted exact threshold problem belongs to $\mathrm P$ or is $\mathrm{NP}$-hard.
The following partial results are proved below:
$$
(1+m+\tau+L+\operatorname{bits}(\varepsilon)+\varepsilon^{-1})^{O(1)}.
$$
In particular, this bound depends polynomially on the encoding length of $\rho$, rather than on its numerical value.
The second and third results advance beyond the results in the supplied notes.
Set
$$
s=a+b,\qquad r=1-s.
$$
The hypotheses imply $0<s<1$ and $0<r<1$.
Conditional on survival, the probability $v_\ell$ that a message is in state $1$ satisfies
$$
v_{\ell+1}=a+rv_\ell.
$$
Solving this recurrence and multiplying by the survival probability $p^d$ gives
$$
\begin{aligned}
q_{d,0}(0)&=p^d\frac{b+ar^d}{s},
&
q_{d,1}(0)&=p^d\frac{b(1-r^d)}{s},
\\
q_{d,0}(1)&=p^d\frac{a(1-r^d)}{s},
&
q_{d,1}(1)&=p^d\frac{a+br^d}{s}.
\end{aligned}
$$
In particular, with $c_d=(pr)^d$,
$$
q_{d,0}(0)-q_{d,1}(0)=c_d,
\qquad
q_{d,0}(1)-q_{d,1}(1)=-c_d.
$$
If $p=0$, every observed count is zero, so $B_\rho(x)=\theta$ for every attack. The decision answer is then yes exactly when $t=0$. Henceforth assume $p>0$.
The posterior is defined on every nonnegative integer count vector. Indeed:
Consequently its denominator is positive in every case.
Write
$$
\lambda_{d,i}(x)
=
\rho\bigl[(\mu_d-x_d)q_{d,1}(i)+x_dq_{d,0}(i)\bigr].
$$
The total observed-count mean is independent of the attack:
$$
\sum_{d,i}\lambda_{d,i}(x)
=
\Lambda
:=
\rho\sum_d\mu_dp^d.
$$
Thus the empty count vector has probability $e^{-\Lambda}>0$ under every attack.
This section supplies a self-contained proof of the selection result used later.
Let $e_{d,i}$ be the unit count vector for coordinate $(d,i)$, and define
$$
\Delta_d(n)=b(n+e_{d,1})-b(n+e_{d,0}).
$$
For $d<e$, I claim that
$$
\Delta_d(n)\geq\Delta_e(n)\geq0
$$
for every count vector $n$, with both inequalities strict at $n=0$.
First suppose $a,b>0$. Define
$$
\phi(z)=\frac{z}{1+z},
\qquad
Z(n)=\frac{\theta H_1(n)}{(1-\theta)H_0(n)}.
$$
Then $Z(n)>0$ and $b(n)=\phi(Z(n))$. Adding a state-$1$ or state-$0$ observation multiplies the posterior odds by, respectively,
$$
u_d=\frac{a+br^d}{a(1-r^d)},
\qquad
v_d=\frac{b(1-r^d)}{b+ar^d}.
$$
Here $u_d>1>v_d>0$. Moreover,
$$
\frac{d}{dy}\frac{a+by}{a(1-y)}
=
\frac{a+b}{a(1-y)^2}>0,
$$
and
$$
\frac{d}{dy}\frac{b(1-y)}{b+ay}
=
-\frac{b(a+b)}{(b+ay)^2}<0.
$$
Since $r^d>r^e$, we have $u_d>u_e$ and $v_d<v_e$. The strict monotonicity of $\phi$ therefore gives
$$
\Delta_d(n)
=
\phi(Z(n)u_d)-\phi(Z(n)v_d)
>
\Delta_e(n)>0.
$$
If $a=0$, a state-$1$ observation forces posterior $1$. Hence $\Delta_d(n)=0$ if $n$ already contains such an observation. Otherwise both likelihoods are positive, and
$$
\Delta_d(n)=1-\phi\bigl(Z(n)(1-r^d)\bigr).
$$
Because $1-r^d$ increases strictly with $d$, this expression is positive and decreases strictly with $d$.
If $b=0$, a state-$0$ observation forces posterior $0$. Thus $\Delta_d(n)=0$ if $n$ already contains a state-$0$ observation. Otherwise,
$$
\Delta_d(n)=\phi\left(\frac{Z(n)}{1-r^d}\right),
$$
which is positive and decreases strictly with $d$.
These cases prove the claim, including strictness at the empty vector.
For independent Poisson coordinates with means $\lambda_j$, and any bounded function $f$,
$$
\frac{\partial}{\partial\lambda_j}\mathbb E_\lambda[f(N)]
=
\mathbb E_\lambda[f(N+e_j)-f(N)].
$$
To justify differentiation, write the expectation as
$$
e^{-\sum_j\lambda_j}
\sum_n f(n)\prod_j\frac{\lambda_j^{n_j}}{n_j!}.
$$
The series and its differentiated series converge locally uniformly, as follows by bounding their absolute values using exponential series. This also supplies an analytic extension at zero means.
Applying the identity to the fixed function $b(n)$ yields
$$
\frac{\partial B_\rho(x)}{\partial x_d}
=
-\rho c_d\,\mathbb E_x[\Delta_d(N)].
$$
Each derivative is strictly negative: $\Delta_d$ is nonnegative everywhere and positive at $N=0$, an event of positive probability.
Furthermore, $d<e$ implies $c_d>c_e>0$. The pointwise ordering above therefore gives
$$
\frac{\partial B_\rho(x)}{\partial x_d}
<
\frac{\partial B_\rho(x)}{\partial x_e}
<0.
$$
Strictness follows from the empty-count event.
Order the support as $d_1<\cdots<d_\tau$, and define
$$
x^*_{d_j}
=
\min\left\{
\mu_{d_j},
\max\left\{0,\kappa-\sum_{\ell<j}\mu_{d_\ell}\right\}
\right\}.
$$
Theorem. For $p>0$, this is the unique minimizer of $B_\rho(x)$ over feasible attacks.
Proof. The feasible set is compact and $B_\rho$ is continuous, so a minimizer exists.
Every minimizer exhausts the budget. Otherwise, since $\sum_d\mu_d=1\geq\kappa$, some coordinate has remaining capacity; increasing it slightly preserves feasibility and strictly decreases $B_\rho$.
Suppose a budget-exhausting vector has $d<e$ with $x_d<\mu_d$ and $x_e>0$. For sufficiently small $\eta>0$, transferring mass $\eta$ from $e$ to $d$ remains feasible. Along this transfer,
$$
\frac{d}{d\eta}B_\rho(x+\eta e_d-\eta e_e)
=
\frac{\partial B_\rho}{\partial x_d}
-
\frac{\partial B_\rho}{\partial x_e}
<0.
$$
Such a vector cannot minimize $B_\rho$.
A vector with no such pair fills an initial sequence of types, possibly fills the next partially, and leaves every subsequent type uncorrupted. Budget exhaustion uniquely determines this vector as $x^*$. $\square$
This proof is independent of the finite-source result in the [cited AAMAS paper](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p2234.pdf).
Sorting and rational prefix arithmetic compute $x^*$ in polynomial time. Its coordinates have $O(L)$ bits: the product of the input denominators supplies a common denominator of $O(L)$ bits, and all relevant masses lie in $[0,1]$. A conservative elementary-arithmetic bound is
$$
O\bigl(L+\tau L^3+\tau\log(\tau+1)\log(m+1)\bigr).
$$
Define the optimal gain
$$
G^*=B_\rho(0)-B_\rho(x^*).
$$
The original decision problem is precisely whether $G^*\geq t$.
Let
$$
f(z)=\frac{1}{1+e^{-z}}.
$$
Then $0<f(z)<1$ and
$$
0<f'(z)\leq\frac14.
$$
Lemma. Let $N_1,\ldots,N_n$ be independent Poisson variables with rational means $\lambda_i\geq0$. Suppose $\alpha$ and $w_i$ are logarithms of positive rationals, and let $S$ denote the total encoding length of these rational data. For rational $0<\varepsilon<1$, one can approximate
$$
E=\mathbb E f\left(\alpha+\sum_{i=1}^n w_iN_i\right)
$$
by a rational number with absolute error at most $\varepsilon$, deterministically in time
$$
(1+n+S+\operatorname{bits}(\varepsilon)+\varepsilon^{-1})^{O(1)}.
$$
The crucial point is that this running time has no polynomial dependence on the numerical values of the large means.
Write $d_K$ for Kolmogorov distance, the supremum of the difference between distribution functions.
We use the classical Berry–Esseen theorem in the following deliberately loose form: for independent identically distributed variables with mean $\mu$, positive variance $v$, and finite third absolute central moment $\beta$,
$$
d_K\left(\sum_{j=1}^{\ell}X_j,\mathcal N(\ell\mu,\ell v)\right)
\leq
\frac{\ell\beta}{(\ell v)^{3/2}}.
$$
The admissibility of constant $1$ follows, for example, from the stronger constants discussed in [Korolev and Shevtsova](https://arxiv.org/pdf/0912.2795).
Here is its implication for a Poisson variable. If $P_h\sim\operatorname{Pois}(h)$, then
$$
\mathbb E|P_h-h|^3
\leq
\mathbb E(P_h+h)^3
=
h+6h^2+8h^3.
$$
The last equality follows from
$$
\mathbb EP_h=h,\quad
\mathbb EP_h^2=h+h^2,\quad
\mathbb EP_h^3=h+3h^2+h^3.
$$
For fixed $\lambda>0$, split $\operatorname{Pois}(\lambda)$ into $\ell$ independent $\operatorname{Pois}(\lambda/\ell)$ variables. The Berry–Esseen hypotheses hold because their variance is positive and all their moments are finite. It follows that
$$
d_K\bigl(\operatorname{Pois}(\lambda),\mathcal N(\lambda,\lambda)\bigr)
\leq
\frac1{\sqrt{\lambda}}
+
\frac{6\sqrt{\lambda}}{\ell}
+
\frac{8\lambda^{3/2}}{\ell^2}.
$$
The distribution on the left is independent of $\ell$. Letting $\ell$ tend to infinity proves
$$
d_K\bigl(\operatorname{Pois}(\lambda),\mathcal N(\lambda,\lambda)\bigr)
\leq\frac1{\sqrt{\lambda}}.
$$
For any smooth monotone function $g$ taking values in $[0,1]$,
$$
|\mathbb Eg(X)-\mathbb Eg(Y)|\leq d_K(X,Y).
$$
Indeed, integration against the tail distributions gives a bound by
$$
d_K(X,Y)\int_{\mathbb R}|g'(u)|\,du,
$$
and the integral is at most $1$. This applies to $g(u)=f(c+wu)$ for every real $c,w$, including negative $w$.
The case $n=0$ requires only evaluation of $f(\alpha)$, so assume $n\geq1$. Put
$$
\delta=\frac{\varepsilon}{20},
\qquad
H=\left(\frac n\delta\right)^2.
$$
Call a coordinate large if $\lambda_i\geq H$, and small otherwise.
Replace each large $N_i$ by an independent normal variable
$$
Y_i\sim\mathcal N(\lambda_i,\lambda_i).
$$
Conditioning on all other coordinates makes the integrand a monotone function of the coordinate being replaced. Therefore the preceding bound and a telescoping argument give total expectation error at most
$$
\sum_{\text{large }i}\lambda_i^{-1/2}
\leq\frac n{\sqrt H}
=\delta.
$$
The weighted sum of the replacement normals is a single normal variable:
$$
\sum_{\text{large }i}w_iY_i=M+\sigma Z,
$$
where $Z\sim\mathcal N(0,1)$ is independent of the small coordinates, and
$$
M=\sum_{\text{large }i}\lambda_iw_i,
\qquad
\sigma^2=\sum_{\text{large }i}\lambda_iw_i^2.
$$
If there are no large coordinates, set $M=\sigma=0$.
Let
$$
T=\sum_{\text{small }i}N_i,
\qquad
\Lambda_s=\sum_{\text{small }i}\lambda_i<nH.
$$
Thus $T\sim\operatorname{Pois}(\Lambda_s)$. Choose
$$
K=
\left\lceil2nH\right\rceil
+
\left\lceil\log_2(1/\delta)\right\rceil
+2.
$$
Markov’s inequality applied to $2^T$, together with $\mathbb E2^T=e^{\Lambda_s}$ and $e<4$, gives
$$
\Pr(T>K)
\leq2^{-K}e^{\Lambda_s}
\leq2^{2nH-K}
\leq\delta.
$$
Because the integrand lies in $[0,1]$, replacing the expectation by its conditional expectation given $T\leq K$ changes its value by at most $\delta$.
Notice that
$$
K=O\bigl(n^3\delta^{-2}+\log(1/\delta)\bigr),
$$
regardless of the numerical values of the large means.
The logarithm of a positive rational with encoding length at most $S$ has absolute value at most $S\log 2$. We may therefore take
$$
W=S+1
$$
as a bound for every $|w_i|$.
Put
$$
\eta=\frac{\delta}{K+1}.
$$
For each small coordinate, first approximate $w_i$ by a rational within $\eta/2$, then round that approximation to a nearest multiple $\eta s_i$, where $s_i$ is an integer. This avoids needing an exact comparison involving an irrational logarithm and guarantees
$$
|w_i-\eta s_i|\leq\eta.
$$
On $T\leq K$,
$$
\left|
\sum_{\text{small }i}w_iN_i
-
\eta\sum_{\text{small }i}s_iN_i
\right|
\leq\eta K<\delta.
$$
The Lipschitz bound for $f$ makes the resulting expectation error at most $\delta/4$.
Furthermore,
$$
|s_i|\leq\frac{W+1}{\eta}.
$$
Consequently the integer score
$$
z=\sum_{\text{small }i}s_iN_i
$$
lies, on $T\leq K$, in $[-D,D]$, where
$$
D=
\left\lceil\frac{K(W+1)}{\eta}\right\rceil
=
O\left(\frac{WK^2}{\delta}\right).
$$
Introduce formal variables $y,u$ and form the Laurent polynomial
$$
\prod_{\text{small }i}
\left(
\sum_{k=0}^K
\frac{\lambda_i^k}{k!}\,y^k u^{s_i k}
\right),
$$
discarding terms with $y$-degree greater than $K$ during multiplication.
Let $c_{k,z}$ be the resulting coefficient of $y^ku^z$. It is exactly the unnormalized Poisson weight of small count vectors having total count $k$ and rounded score $z$.
The normalizing constant is
$$
C=\sum_{k,z}c_{k,z}
=
\sum_{k=0}^K\frac{\Lambda_s^k}{k!}.
$$
This follows by setting $u=1$ and applying the multinomial identity. Thus
$$
\pi_z=\frac{\sum_{k=0}^Kc_{k,z}}{C}
$$
is the conditional distribution of the rounded score given $T\leq K$.
The table has at most $(K+1)(2D+1)$ entries. Direct multiplication uses
$$
O\bigl(nK^2(D+1)\bigr)
$$
rational arithmetic operations.
These operations have polynomial bit complexity. If the reduced denominators of the small means are $Q_i$, every coefficient denominator divides
$$
\left(\prod_{\text{small }i}Q_i\right)^K(K!)^n.
$$
This common denominator has
$$
O\bigl(KS+nK\log(K+1)\bigr)
$$
bits. Moreover, the sum of all retained nonnegative coefficients is at most $e^{\Lambda_s}\leq e^{nH}$, whose logarithm is polynomially bounded in $K$. Hence coefficient numerators and normalized probabilities also have polynomial bit length.
We have reduced the expectation to
$$
\sum_{z=-D}^D
\pi_z\,
\mathbb E_Z f(A+\eta z+\sigma Z),
\qquad
A=\alpha+M.
$$
First approximate $A$ and $\sigma$ by rationals $\widetilde A,\widetilde\sigma$, with $\widetilde\sigma\geq0$, satisfying
$$
|A-\widetilde A|\leq\delta,
\qquad
|\sigma-\widetilde\sigma|\leq\delta.
$$
Coupling the two normal expressions using the same $Z$ shows that this changes each expectation by at most
$$
\frac14\bigl(\delta+\delta\mathbb E|Z|\bigr)
\leq\frac{\delta}{2}.
$$
These absolute approximations require only polynomial precision. Indeed, $\lambda_i\leq2^S$ and $|w_i|\leq W$. Approximating the logarithms to absolute error of order
$$
\frac{\delta^2}{n2^S(W+1)}
$$
suffices to compute $A$ to error $O(\delta)$ and $\sigma^2$ to error $O(\delta^2)$. The inequality
$$
|\sqrt v-\sqrt{\widetilde v}|
\leq\sqrt{|v-\widetilde v|}
$$
for nonnegative $v,\widetilde v$ then controls the square root. The required number of bits is polynomial in $S+\log(n+1)+\log(1/\delta)$.
For the normal integration, take
$$
R=\lceil1/\delta\rceil
$$
and partition $[-R,R]$ into intervals of length at most $\delta$. There are $J=O(\delta^{-2})$ intervals. Assign each interior interval’s normal probability to its left endpoint, and assign the two tail probabilities to $-R$ and $R$.
For any monotone $g:\mathbb R\to[0,1]$, the interior approximation error is at most
$$
\max_j\Pr(Z\text{ lies in interval }j)
\sum_j\bigl(g(u_{j+1})-g(u_j)\bigr)
\leq\delta,
$$
because the standard normal density is bounded by $1$. The tail error is at most
$$
\Pr(|Z|>R)\leq R^{-2}\leq\delta^2
$$
by Chebyshev’s inequality. Therefore this discrete normal approximation changes each expectation by at most $2\delta$, uniformly in its shift and scale.
Approximate the discrete probabilities with total absolute error at most $\delta$, and each required logistic value within $\delta$. Clipping the numerical probability and logistic approximations to nonnegative values and $[0,1]$, respectively, gives an additional error at most $3\delta$.
All these numerical computations have polynomial bit complexity. For completeness:
$$
\log v
=
2\sum_{j=0}^{\infty}
\frac{z^{2j+1}}{2j+1},
\qquad
z=\frac{v-1}{v+1},
$$
where $|z|\leq1/3$.
Collecting the errors gives a bound below
$$
\delta+\delta+\delta+\delta+2\delta+3\delta
=
9\delta
<
\varepsilon.
$$
Every table size, arithmetic bit length and numerical evaluation count is polynomial in $n,S,\varepsilon^{-1}$ and the accuracy encoding length. This proves the lemma. $\square$
Set
$$
\alpha=\log\frac{\theta}{1-\theta},
\qquad
w_{d,i}=\log\frac{q_{d,1}(i)}{q_{d,0}(i)}.
$$
All ratios are positive rationals. The posterior has the representation
$$
b(N)
=
f\left(\alpha+\sum_{d,i}w_{d,i}N_{d,i}\right).
$$
The lemma therefore applies directly with at most $2\tau$ Poisson coordinates.
The transition probabilities and means at $x=0,x^*$ are computable exactly in polynomial time and have $O(mL)$ bits each. For example, the displayed transition formulas involve rational powers of exponent at most $m$ and rational operations on the input parameters. Thus the total rational-data length used in the lemma is polynomial in $m,\tau,L$.
These cases also reduce to the lemma.
Suppose $a=0$. Any state-$1$ observation forces posterior $1$. Let
$$
A_1(x)=\sum_d\lambda_{d,1}(x)
=
\rho\sum_d(\mu_d-x_d)(pr)^d.
$$
Independence of the two sets of counts gives
$$
B_\rho(x)
=
1-e^{-A_1(x)}
+
e^{-A_1(x)}
\mathbb E f\left(
\alpha+\sum_d\log(1-r^d)N_{d,0}
\right).
$$
Every logarithm has a positive rational argument.
If $b=0$, any state-$0$ observation forces posterior $0$. With
$$
A_0(x)=\sum_d\lambda_{d,0}(x)
=
\rho\sum_dx_d(pr)^d,
$$
we similarly obtain
$$
B_\rho(x)
=
e^{-A_0(x)}
\mathbb E f\left(
\alpha-\sum_d\log(1-r^d)N_{d,1}
\right).
$$
The remaining expectation has at most $\tau$ coordinates. The exponential factors can be approximated in polynomial time: when their nonnegative rational argument exceeds an integer of order $\log(1/\varepsilon)$, the factor can already be replaced by zero within the allocated error.
Applying these procedures to $x=0$ and $x=x^*$, with appropriately divided error budgets, produces a rational $\widehat G$ satisfying
$$
|\widehat G-G^*|\leq\varepsilon
$$
in deterministic time
$$
(1+m+\tau+L+\operatorname{bits}(\varepsilon)+\varepsilon^{-1})^{O(1)}.
$$
Here $L$ includes the encoding lengths of $\rho,\kappa,t$.
Consequently, under the promise
$$
|G^*-t|\geq\gamma,
$$
using accuracy $\gamma/4$ decides the comparison in time
$$
(1+m+\tau+L+\operatorname{bits}(\gamma)+\gamma^{-1})^{O(1)}.
$$
In particular, the threshold problem with a specified inverse-polynomial gap is in $\mathrm P$.
This is an additive approximation result. It supplies no relative approximation guarantee for an arbitrarily small positive gain.
The following family rules out a universal polynomial-bit separation bound, even for one type.
Take
$$
D=\{1\},\quad
\mu_1=1,\quad
p=1,\quad
a=b=\frac14,\quad
\theta=\frac12,\quad
\kappa=\frac12,\quad
t=\frac12.
$$
The optimal attack is $x_1^*=1/2$.
Write $S=N_{1,1}-N_{1,0}$. The likelihood ratios are $3$ and $1/3$, so
$$
b(N)=\frac{3^S}{1+3^S}=f(S\log3).
$$
Under $x^*$, the two counts are independent $\operatorname{Pois}(\rho/2)$ variables. Their joint distribution is invariant under exchanging them, which sends $S$ to $-S$. Since
$$
f(u)+f(-u)=1,
$$
we obtain the exact identity
$$
B_\rho(x^*)=\frac12.
$$
Thus
$$
G^*=B_\rho(0)-\frac12,
\qquad
t-G^*=1-B_\rho(0)>0.
$$
The strict inequality follows because the posterior is strictly below $1$ on every finite count vector.
Under the honest society,
$$
N_{1,1}\sim\operatorname{Pois}(3\rho/4),
\qquad
N_{1,0}\sim\operatorname{Pois}(\rho/4).
$$
For every real $S$, the arithmetic–geometric mean inequality gives
$$
\frac1{1+3^S}\leq\frac12\,3^{-S/2}.
$$
Using independence and the Poisson generating function,
$$
\begin{aligned}
1-B_\rho(0)
&\leq
\frac12\,\mathbb E3^{-S/2}
\\
&=
\frac12
\exp\left[
\frac{3\rho}{4}(3^{-1/2}-1)
+
\frac{\rho}{4}(3^{1/2}-1)
\right]
\\
&=
\frac12e^{-c\rho},
\end{aligned}
$$
where
$$
c=1-\frac{\sqrt3}{2}>0.
$$
The empty-count event also supplies the lower bound
$$
1-B_\rho(0)\geq\frac12e^{-\rho}.
$$
Therefore
$$
\frac12e^{-\rho}
\leq
t-G^*
\leq
\frac12e^{-c\rho}.
$$
Now choose the binary-encoded rational $\rho=2^h$. All other parameters are fixed, so the input length is $L=\Theta(h)$, while
$$
0<t-G^*\leq\frac12e^{-c2^h}.
$$
For every fixed polynomial $P$, this is smaller than $2^{-P(L)}$ for all sufficiently large $h$.
Hence no universal lower bound of the form
$$
G^*\neq t
\quad\Longrightarrow\quad
|G^*-t|\geq2^{-\operatorname{poly}(m,\tau,L)}
$$
can hold.
The family itself has the exact answer no, by the identity above. Its consequence is specifically the failure of the proposed universal separation bound.
Some unrestricted instances have immediate exact answers:
$$ G^*\leq1-e^{-\Lambda}<1. $$
For general thresholds, the real optimization variables have been eliminated and deterministic approximation is efficient for binary-encoded $\rho$. Increasing precision eventually decides every unequal comparison. These facts do not give a polynomial running-time bound for unrestricted exact comparison, and they do not handle arbitrary equality instances.
The small-gap family shows that a universal polynomial-bit separation argument is unavailable. A complete resolution still requires an exact comparison method using additional structure, or a valid hardness reduction to this particular channel family.
⟨structured verdict parsed — rendered above⟩
Overall assessment: valid partial progress, with minor expositional issues. The output proves the optimal attack’s structure, gives a sound deterministic additive approximation argument, and establishes the claimed failure of a universal polynomial-bit separation bound. It explicitly leaves the exact decision problem unresolved.
The distinction matters: computing the optimal attack in polynomial time does not establish that its expected gain can be compared exactly with a rational threshold in polynomial time.
The transition formulas are correct. The recurrence
$$
v_{\ell+1}=a+(1-a-b)v_\ell
$$
has the stated solution for both initial states, and multiplication by $p^d$ correctly accounts for survival.
The assumptions imply
$$
0<a+b<1,\qquad 0<r<1.
$$
Subtracting the displayed transition probabilities gives exactly
$$
q_{d,0}(0)-q_{d,1}(0)=(pr)^d,
\qquad
q_{d,0}(1)-q_{d,1}(1)=-(pr)^d.
$$
The treatment of $p=0$ is correct: all observed counts vanish, the posterior equals $\theta$, and every attack has zero gain.
For $p>0$, the posterior denominator is positive on every nonnegative integer count vector:
The identity
$$
\Lambda=\rho\sum_d\mu_dp^d
$$
is correct and independent of the attack. Consequently, the empty-count event has the stated positive probability.
No substantive issue in this section.
For positive mutation rates, the likelihood-ratio multipliers $u_d$ and $v_d$ are correct. Both displayed derivatives are correct. Since $r^d$ decreases strictly with distance, the argument establishes
$$
\Delta_d(n)>\Delta_e(n)>0
$$
for $d<e$.
The zero-rate cases are also handled correctly:
On the remaining count vectors, the stated formulas give the required distance ordering. Strictness at the empty vector follows from $\theta\in(0,1)$ and $0<r<1$.
The differentiation identity is correct. Boundedness of the function supplies the stated local uniform convergence of the series and its derivatives, including the extension at zero means.
The attack changes the two coordinate means at rates $\rho c_d$ and $-\rho c_d$. Thus the derivative formula
$$
\frac{\partial B_\rho(x)}{\partial x_d}
=-\rho c_d\,\mathbb E_x[\Delta_d(N)]
$$
has the correct sign.
The pointwise nonnegativity and positive empty-count contribution justify strict negativity. Since
$$
c_d>c_e>0
$$
for $d<e$, the strict ordering of derivatives also follows.
The feasible set is compact, and continuity gives existence of a minimizer. The budget-exhaustion argument is valid whenever a minimizer has slack.
The exchange argument preserves feasibility for sufficiently small positive transfer and strictly decreases $B_\rho$. It therefore excludes every vector containing a farther corrupted type while a closer type retains capacity.
The remaining feasible, budget-exhausting vector is uniquely the displayed prefix-filling vector. The cases $\kappa=0$ and $\kappa=1$ are consistent with this conclusion.
The rational bit-length argument and conservative polynomial running-time bound are valid. In particular, the use of a product of input denominators gives a common denominator of $O(L)$ bits.
The unique optimal attack theorem is established. It does not, by itself, resolve exact threshold comparison.
The Berry–Esseen statement is sufficiently precise for its application. Constant $1$ is valid; the [cited Korolev–Shevtsova paper](https://arxiv.org/pdf/0912.2795) supplies a stronger bound. The Poisson summands satisfy the required independence, identical distribution, positive variance, and finite third absolute central moment.
The moment calculation
$$
\mathbb E(P_h+h)^3=h+6h^2+8h^3
$$
is correct. Substitution into the theorem yields exactly the displayed bound involving $\ell$. Letting $\ell$ tend to infinity is legitimate because the distribution being compared remains fixed.
The resulting estimate
$$
d_K\bigl(\operatorname{Pois}(\lambda),\mathcal N(\lambda,\lambda)\bigr)
\leq\lambda^{-1/2}
$$
is therefore justified.
The monotone-function expectation bound correctly uses total variation through the integral of $|g'|$. It applies to either sign of the weight.
The replacement argument correctly conditions on all other coordinates. Independence permits the telescoping comparison, whose accumulated error is at most $\delta$.
The expressions for $M$ and $\sigma^2$ are correct. Zero weights and the absence of large coordinates cause no difficulty.
The total small count is Poisson with the stated mean. The generating-function and Markov bounds give
$$
\Pr(T>K)\leq\delta
$$
with the chosen $K$.
Replacing an expectation of a function valued in $[0,1]$ by its conditional expectation changes it by at most the discarded probability. The conditioning event has positive probability.
The stated polynomial bound on $K$ is correct.
The logarithm magnitude bound is valid under ordinary binary rational encoding. Approximating before rounding avoids the need to decide an exact irrational comparison.
The accumulated score error on $T\leq K$ is less than $\delta$, and the logistic Lipschitz constant gives the stated expectation error. The bound on the integer score range is correct.
The Laurent-polynomial coefficients represent exactly the asserted unnormalized weights. Truncating intermediate products is safe because count degrees are nonnegative.
The normalization identity is correct. It also covers zero means and an empty set of small coordinates.
The table size and direct multiplication operation count are valid. The proposed common denominator bounds the coefficient denominators, and the nonnegative coefficient-sum bound controls numerator lengths. Consequently, exact rational arithmetic has polynomial bit complexity in the stated parameters.
The coupling error for approximating $A$ and $\sigma$ is correct. The precision discussion accounts for exponentially large means through their encoding lengths. Its unspecified constant factors are routine precision choices, rather than a substantive gap.
The discrete normal approximation has an error bound independent of the shift and scale for the functions actually used here. The tail estimate and numerical probability/value error budgets are valid.
Minor issue: the displayed interior-error formula is stated for “any monotone” function, but contains
$$
\sum_j\bigl(g(u_{j+1})-g(u_j)\bigr).
$$
For a decreasing function this quantity is nonpositive, so the displayed inequality is false as written.
Minimum clarification: restrict that displayed calculation to nondecreasing functions, or use absolute increments. The application already uses nondecreasing functions because $\widetilde\sigma\geq0$, so this does not affect the approximation result.
The proposed elementary numerical procedures have polynomial cost at the required tolerances. The collected error budget is safely below $\varepsilon$.
Minor issue: the opening claim covers every rational $\varepsilon>0$, whereas the lemma and its parameter choices assume $0<\varepsilon<1$.
Minimum clarification: state the trivial output convention for $\varepsilon\geq1$, or restrict the accuracy claim to $0<\varepsilon<1$. This is an omitted routine edge case.
The approximation lemma is sound in substance.
For positive mutation rates, the log-likelihood representation is correct, with positive rational logarithm arguments. Exact transition probabilities and means have polynomial encoding length in $m,\tau,L$, as claimed.
For $a=0$, the formula for $A_1(x)$ and the decomposition according to whether any state-$1$ observation occurs are correct. Independence justifies the remaining expectation.
For $b=0$, the analogous formula for $A_0(x)$ and its multiplicative decomposition are also correct.
Approximating the exponential factors does not introduce dependence polynomial in the numerical value of $\rho$. Applying divided error budgets to the two expectations gives the stated additive approximation for $G^*$.
Under the promised gap, accuracy $\gamma/4$ is sufficient to determine the comparison. The polynomial-time claim for a specified inverse-polynomial gap is justified.
This establishes approximation and promised-gap comparison, not unrestricted exact comparison.
Every parameter in the proposed family satisfies the task’s assumptions.
The likelihood ratios are indeed $3$ and $1/3$. Under the optimal attack, the two count means equal $\rho/2$, and exchange symmetry establishes
$$
B_\rho(x^*)=\frac12.
$$
The identity
$$
t-G^*=1-B_\rho(0)>0
$$
is correct. Strict positivity also follows from the positive empty-count contribution used later in the proof.
The arithmetic–geometric mean inequality is applied correctly. The Poisson generating-function calculation gives the stated constant
$$
c=1-\frac{\sqrt3}{2}>0.
$$
The empty-count lower bound is also correct. Hence both sides of
$$
\frac12e^{-\rho}\leq t-G^*\leq\frac12e^{-c\rho}
$$
are justified.
Encoding $\rho=2^h$ gives $L=\Theta(h)$ with the remaining parameters fixed. The upper bound consequently becomes smaller than $2^{-P(L)}$ for every fixed polynomial $P$, for sufficiently large $h$.
The separation-bound obstruction is proved. The output correctly avoids claiming that this obstruction proves hardness.
The listed immediate exact answers are correct, including the bound for $t=1$. The common empty-count contribution gives the displayed strict upper bound on the gain.
The final distinction between unequal comparisons and equality instances is also correct. Increasing accuracy can eventually resolve a nonzero gap, but the supplied running-time bound depends on the reciprocal accuracy. The small-gap family prevents the proposed universal separation shortcut.
Major unresolved requirement: the task asks for polynomial-time exact decision or an $\mathrm{NP}$-hardness result. Neither is established. This is an acknowledged incompleteness, not a false mathematical step.
Minimum additional work needed: provide a verified exact comparison method with polynomial running time for all allowed inputs, including equality, or a valid hardness reduction for this precise model. The present selection and approximation results do not supply either.
The direction is promising: the partial results substantially simplify the optimization and identify the remaining comparison problem precisely.
⟨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.