Answer: \(\text{Polynomial-time solvable}\)
Proposition 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor any comparison matrix R, the negative log-posterior L(·|R) is (1/σ2)-strongly convex, and thus ad- mits a unique minimizer Θ∗ f,σ2(R) ∈RA. Since it is the mode of the posterior, Θ∗ f,σ2(R) is com- monly known as the maximum a posteriori (MAP) estima- tor.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix a finite-support \(K\)-nary GBT root law and positive rational prior variance \(\sigma^2\). An instance gives \(m\) alternatives, a positive integer population scale \(N\), report types \(t=(a_t,b_t,r_t)\) with rational masses \(\mu_t\) summing to \(1\), and rational \(\varepsilon>0\). Output a rational vector within \(\ell_2\)-distance \(\varepsilon\) of the minimizer of \(J(\theta)=\frac{1}{2\sigma^2}\sum_{a=1}^m\theta_a^2+N\sum_{t\in T}\mu_t[\Phi_f(\theta_{a_t}-\theta_{b_t})-r_t(\theta_{a_t}-\theta_{b_t})]\).
Fix an integer \(K\geq2\) and a rational \(\sigma^2>0\). The root law is uniform on \(S_K=\{2(k-1)/(K-1)-1:1\leq k\leq K\}\), with \(\Phi_f(x)=\log(K^{-1}\sum_{r\in S_K}e^{rx})\).
A society is given by its support: a list \(T\) of \(\tau\geq1\) report types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
An instance specifies \(m\geq2\) alternatives, a binary positive integer population scale \(N\), types \(t=(a_t,b_t,r_t)\) with distinct \(a_t,b_t\in\{1,\ldots,m\}\) and \(r_t\in S_K\), and a binary rational \(\varepsilon>0\). Reversing a report replaces \((a,b,r)\) by \((b,a,-r)\); each listed mass contributes once.
Over \(\theta\in\mathbb R^m\), define \(J(\theta)=\frac{1}{2\sigma^2}\sum_{a=1}^m\theta_a^2+N\sum_{t\in T}\mu_t[\Phi_f(\theta_{a_t}-\theta_{b_t})-r_t(\theta_{a_t}-\theta_{b_t})]\), and let \(\theta^*\) be its unique minimizer.
The computational problem is to output \(\widehat\theta\in\mathbb Q^m\) satisfying \(\|\widehat\theta-\theta^*\|_2\leq\varepsilon\). Let \(L\) be the total binary input length, including \(N\), the masses, and \(\varepsilon\); \(K\) and \(\sigma^2\) are fixed constants.
Is this approximation problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite comparison data, the negative log-posterior is \((1/\sigma^2)\)-strongly convex and has a unique minimizer; the accompanying computational claim supplies no polynomial bound in binary input length. [Source](https://arxiv.org/html/2308.08644v2)
No result settling this exact rational-mass approximation problem was located in the literature search.
Claim. The approximation problem is solvable by a deterministic algorithm in time polynomial in \(m,\tau,L\), for every fixed \(K\geq2\) and fixed rational \(\sigma^2>0\).
The proof requires more than strong convexity: it must control the search radius, numerical evaluation, and the bit complexity of optimization. The [cited paper](https://arxiv.org/html/2308.08644v2) establishes strong convexity in its finite-data setting; the argument below supplies these additional controls for the stated rational-mass problem.
1. Convexity, existence, and quantitative bounds
Write \(v_t=e_{a_t}-e_{b_t}\), so that \(\|v_t\|_2=\sqrt2\). For real \(x\), define
\[ p_r(x)=\frac{e^{rx}}{\sum_{s\in S_K}e^{sx}}. \]
Then
\[ \Phi_f'(x)=\sum_{r\in S_K}r\,p_r(x),\qquad \Phi_f''(x)=\sum_{r\in S_K}(r-\Phi_f'(x))^2p_r(x)\geq0. \]
Because \(S_K\subseteq[-1,1]\), we also have \(|\Phi_f'(x)|\leq1\). Consequently,
\[ \nabla J(\theta)=\frac{\theta}{\sigma^2} +N\sum_{t\in T}\mu_t \bigl(\Phi_f'(v_t^\mathsf T\theta)-r_t\bigr)v_t, \]
and
\[ \nabla^2J(\theta)=\frac1{\sigma^2}I+ N\sum_{t\in T}\mu_t\Phi_f''(v_t^\mathsf T\theta)v_tv_t^\mathsf T \succeq\frac1{\sigma^2}I. \]
Thus \(J\) is \((1/\sigma^2)\)-strongly convex.
For every listed report, the term corresponding to \(r_t\) in the exponential sum gives
\[ \Phi_f(x)-r_tx\geq-\log K. \]
Since the masses sum to \(1\),
\[ J(\theta)\geq\frac{\|\theta\|_2^2}{2\sigma^2}-N\log K. \]
Hence \(J\) is coercive and has a unique minimizer \(\theta^*\).
Symmetry of \(S_K\) gives \(\Phi_f'(0)=0\), whence
\[ \|\nabla J(0)\|_2 =\left\|-N\sum_t\mu_tr_tv_t\right\|_2 \leq\sqrt2N. \]
Strong convexity implies strong monotonicity of the gradient. Applying this to \(0\) and \(\theta^*\), using \(\nabla J(\theta^*)=0\), yields
\[ \frac{\|\theta^*\|_2^2}{\sigma^2} \leq-\nabla J(0)^\mathsf T\theta^* \leq\|\nabla J(0)\|_2\|\theta^*\|_2. \]
It follows, including the case \(\theta^*=0\), that
\[ \|\theta^*\|_2\leq\sqrt2\,\sigma^2N. \]
Set
\[ R=1+2\sigma^2N,\qquad D=\{\theta:\|\theta\|_2\leq R\},\qquad G=\frac R{\sigma^2}+3N. \]
These are rational numbers of bit length \(O(L+1)\), since \(\sigma^2\) is fixed. Moreover, \(\|\theta^*\|_2<R-1\), and for every \(\theta\in D\),
\[ \|\nabla J(\theta)\|_2 \leq\frac R{\sigma^2} +N\sum_t\mu_t\,2\sqrt2 \leq G. \]
Integrating the gradient along line segments in the convex set \(D\) shows that
\[ |J(x)-J(y)|\leq G\|x-y\|_2 \quad\text{for all }x,y\in D. \]
Finally, strong convexity gives the error conversion
\[ J(x)-J(\theta^*)\geq \frac{\|x-\theta^*\|_2^2}{2\sigma^2}. \]
2. Polynomial-time numerical evaluation
We next establish that \(J\) and its gradient can be approximated to any prescribed absolute precision in polynomial bit complexity. This must hold even when a rational score difference has exponentially large numerical magnitude.
For rational \(x\), let \(h=|x|\), and choose \(s=1\) when \(x\geq0\) and \(s=-1\) otherwise. Put
\[ q_r=e^{-(1-sr)h},\qquad Z=\sum_{r\in S_K}q_r,\qquad U=\sum_{r\in S_K}r q_r. \]
The endpoint \(r=s\) belongs to \(S_K\), so its term is exactly \(1\). Therefore
\[ 1\leq Z\leq K,\qquad \Phi_f(x)=h+\log Z-\log K,\qquad \Phi_f'(x)=\frac UZ. \]
All exponentials now have nonpositive arguments.
For completeness, \(e^{-u}\), with rational \(u\geq0\), admits an absolute-error \(2^{-p}\) approximation in time polynomial in the bit length of \(u\) and \(p\):
The Taylor terms are rational, and their exact numerators and denominators have polynomial bit length. Rounding and clipping to \([0,1]\), with a few extra precision bits, preserves the claimed accuracy. The endpoint term can be kept exactly equal to \(1\).
If each \(q_r\) is approximated within \(\zeta\), with nonnegative approximations, then the resulting \(\widetilde Z,\widetilde U\) satisfy
\[ \widetilde Z\geq1,\quad |Z-\widetilde Z|\leq K\zeta,\quad |U-\widetilde U|\leq K\zeta,\quad |\widetilde U|\leq\widetilde Z. \]
Consequently,
\[ \left|\frac UZ-\frac{\widetilde U}{\widetilde Z}\right| \leq2K\zeta, \qquad |\log Z-\log\widetilde Z|\leq K\zeta. \]
Logarithms of rational numbers \(z\in[1,K]\) are also polynomial-time approximable. Explicitly,
\[ \log z=2\sum_{j=0}^{\infty} \frac{w^{2j+1}}{2j+1}, \qquad w=\frac{z-1}{z+1}. \]
Here \(0\leq w\leq(K-1)/(K+1)<1\). Since \(K\) is fixed, \(O(p+1)\) terms give absolute error \(2^{-p}\). The same construction approximates \(\log K\).
These procedures prove the following numerical fact:
Given rational \(\theta\) and positive rational tolerances \(\nu,\eta\), one can compute rational \(j,g\) satisfying
\[ > |j-J(\theta)|\leq\nu,\qquad > \|g-\nabla J(\theta)\|_2\leq\eta, > \]
in time polynomial in \(m,\tau,L\), the bit length of \(\theta\), and the bit lengths of \(\nu,\eta\).
To check accumulation of errors, if every \(\Phi_f\) evaluation has error at most \(a\), its contribution to the objective error is at most \(Na\), because \(\sum_t\mu_t=1\). If every derivative evaluation has error at most \(b\), its contribution to the gradient error is at most \(\sqrt2Nb\). The quadratic and report-linear terms are rational and can be computed exactly.
Thus the required extra precision depends on \(\log N\), not on \(N\). The sums range over the \(\tau\) listed reports; no expansion into individual voters is performed.
3. A finite-precision ellipsoid construction
We record the optimization machinery explicitly to ensure a bit-complexity bound.
Let
\[ E(c,A)=\{x:(x-c)^\mathsf TA^{-1}(x-c)\leq1\}, \]
where \(A\) is positive definite. For dimension \(n\geq2\), a nonzero central-cut normal \(g\) defines the retained halfspace
\[ H=\{x:g^\mathsf T(x-c)\leq0\}. \]
The exact central-cut update is
\[ d=c-\frac{Ag}{(n+1)\sqrt{g^\mathsf TAg}}, \]
\[ B=\frac{n^2}{n^2-1} \left(A-\frac{2}{n+1} \frac{Agg^\mathsf TA}{g^\mathsf TAg}\right). \]
It satisfies \(E(c,A)\cap H\subseteq E(d,B)\). Here is a direct verification. After transforming the original ellipsoid into the unit ball and rotating the cut normal to the first coordinate, the new center is \(-e_1/(n+1)\); the squared semiaxes are \(n^2/(n+1)^2\) in that direction and \(n^2/(n^2-1)\) in perpendicular directions. For a point in the retained half-ball, writing its first coordinate as \(t\in[-1,0]\), its new ellipsoid expression is at most
\[ \frac{(n+1)^2}{n^2} \left(t+\frac1{n+1}\right)^2 +\frac{n^2-1}{n^2}(1-t^2) =1+\frac{2(n+1)}{n^2}t(t+1)\leq1. \]
The exact volume ratio is
\[ q_n=\left(\frac{n^2}{n^2-1}\right)^{n/2} \sqrt{\frac{n-1}{n+1}}. \]
Expanding the logarithms in their convergent power series gives
\[ \log q_n =-\sum_{k=1}^{\infty} \frac1{2k(2k-1)n^{2k-1}} \leq-\frac1{2n}. \]
We now make the updates rational while retaining exponential volume decrease.
Fix in advance an iteration budget \(T\), start with \(c_0=0\), \(A_0=R^2I\), where \(R\geq1\), and set
\[ \alpha=\frac1{64n^2},\qquad \ell=4^{-(T+1)}. \]
Choose a dyadic number \(h\) satisfying
\[ 0<h\leq\frac{\alpha\ell}{4n}. \]
At each iteration:
We verify all needed properties. The exact update obeys
\[ B\succeq\frac14A. \]
Since \(\widehat A\succeq C\succeq B\), induction gives \(\lambda_{\min}(A_i)\geq4^{-i}\). Thus every updated \(B\) has smallest eigenvalue at least \(\ell\).
The center error satisfies
\[ \|\widehat c-d\|_2\leq\sqrt n\,h \leq\alpha\sqrt\ell, \]
so its norm measured using \(B^{-1}\) is at most \(\alpha\). The triangle inequality in that norm proves
\[ E(d,B)\subseteq E(\widehat c,C). \]
For symmetric entrywise rounding, the operator-norm error is at most \(nh\). Hence
\[ C\preceq\widehat A\preceq C+2nhI \preceq(1+\alpha)C. \]
These inequalities prove containment and positive definiteness. They also bound the rounded-update volume ratio by
\[ q_n(1+\alpha)^{3n/2}. \]
Its logarithm is at most
\[ -\frac1{2n}+\frac{3n\alpha}{2} =-\frac1{2n}+\frac3{128n} \leq-\frac1{4n}. \]
Thus every rational update shrinks volume by a factor at most \(e^{-1/(4n)}\).
Finally, this construction has polynomial bit complexity. The grid denominator has \(O(T+\log n)\) bits. Furthermore,
\[ \lambda_{\max}(\widehat A) \leq(1+\alpha)^3\frac{n^2}{n^2-1}\lambda_{\max}(A) <2\lambda_{\max}(A). \]
Therefore matrix magnitudes and accumulated center magnitudes have logarithms bounded polynomially in \(T,\log R,n\). Every stored center and matrix consequently has polynomial bit length. Given cut normals of polynomial bit length, the exact intermediate rational operations also have polynomial bit complexity. The only square root is of a positive rational of polynomial bit length; rational bisection computes the center to the required precision in polynomial time.
We have therefore proved the precise implementation fact needed below: after \(T\) rational central cuts, all containment statements remain valid and
\[ \operatorname{vol}(E_T) \leq e^{-T/(4n)}\operatorname{vol}(E_0), \]
with polynomial arithmetic and bit complexity.
4. The approximation algorithm
Define the rational parameters
\[ \varepsilon_0=\min\{\varepsilon,1\},\qquad \Delta=\frac{\varepsilon_0^2}{4\sigma^2},\qquad \nu=\frac\Delta4,\qquad \eta=\frac{\Delta}{8R},\qquad \rho=\min\left\{1,\frac{\Delta}{4G}\right\}. \]
Each has polynomial bit length. The ball
\[ P=\{y:\|y-\theta^*\|_2\leq\rho\} \]
is contained in \(D\), because \(\|\theta^*\|_2<R-1\) and \(\rho\leq1\). The Lipschitz bound proves that every \(y\in P\) satisfies
\[ J(y)\leq J(\theta^*)+G\rho \leq J(\theta^*)+\frac\Delta4. \]
Compute an integer \(b\geq1\) such that \(R/\rho\leq2^b\), and set
\[ T=8m^2(b+1). \]
Because \(R/\rho\) has polynomial bit length, \(b\) and \(T\) are polynomially bounded in \(m,L\).
Run the rational ellipsoid construction in dimension \(m\), starting with \(E_0=D\). At its current rational center \(x\):
If all \(T\) iterations finish, output the recorded center with smallest recorded value \(j\). There is at least one recorded center, since the initial center \(0\) belongs to \(D\).
We prove correctness.
First, a cut at a center outside \(D\) retains all of \(D\). Indeed, for \(y\in D\),
\[ x^\mathsf T(y-x) \leq\|x\|_2R-\|x\|_2^2<0. \]
Second, if an evaluated center has \(g=0\), then \(\|\nabla J(x)\|_2\leq\eta\). Convexity and \(x,\theta^*\in D\) give
\[ J(x)-J(\theta^*) \leq\nabla J(x)^\mathsf T(x-\theta^*) \leq2R\eta=\frac\Delta4. \]
The strong-convexity error conversion already proves the required approximation in this case.
Now suppose no immediate return occurs. Consider any evaluated center \(x\) for which
\[ J(x)>J(\theta^*)+\Delta. \]
For \(y\in P\), convexity implies
\[ \nabla J(x)^\mathsf T(y-x) \leq J(y)-J(x)<-\frac{3\Delta}{4}. \]
Since \(x,y\in D\), the approximate-gradient error contributes at most
\[ |(g-\nabla J(x))^\mathsf T(y-x)| \leq2R\eta=\frac\Delta4. \]
Consequently,
\[ g^\mathsf T(y-x)<-\frac\Delta2<0. \]
Thus every cut at such a center retains the entire ball \(P\).
If every evaluated center had objective gap greater than \(\Delta\), all cuts would retain \(P\). The containment guarantees in Section 3 would then imply \(P\subseteq E_T\). But, writing \(v_m\) for the volume of the unit ball,
\[ \operatorname{vol}(E_T) \leq e^{-T/(4m)}v_mR^m <v_m\rho^m=\operatorname{vol}(P). \]
The strict inequality follows from \(T=8m^2(b+1)\) and \(\log(R/\rho)\leq b\log2\). This is a contradiction. Hence some recorded center \(x_{\rm good}\) satisfies
\[ J(x_{\rm good})-J(\theta^*)\leq\Delta. \]
The output \(\widehat\theta\) minimizes the recorded approximate objective values, each with absolute error at most \(\nu\). Therefore
\[ J(\widehat\theta) \leq J(x_{\rm good})+2\nu \leq J(\theta^*)+\frac{3\Delta}{2}. \]
Applying strong convexity,
\[ \|\widehat\theta-\theta^*\|_2^2 \leq2\sigma^2\bigl(J(\widehat\theta)-J(\theta^*)\bigr) \leq3\sigma^2\Delta =\frac34\varepsilon_0^2 \leq\varepsilon^2. \]
This establishes the required guarantee.
5. Complexity conclusion
There are polynomially many ellipsoid iterations. Section 3 bounds the bit lengths of their rational centers and matrices. Section 2 supplies polynomial-time objective and gradient evaluations at those centers, at the polynomial-bit tolerances used above. All remaining comparisons and arithmetic are rational operations of polynomial bit complexity.
The algorithm outputs a rational vector and runs in time polynomial in \(m,\tau,L\). Binary encoding of \(N\) does not invalidate this result: the iteration and precision bounds depend on \(\log N\).
⟨structured verdict parsed — rendered above⟩
The argument is correct in substance, with two minor gaps in parameter selection. The numerical oracle, ellipsoid containment, volume reduction, and final approximation guarantee check out. No new mathematical argument is needed; the write-up should specify bounded choices for two parameters whose stated inequalities alone do not ensure polynomial complexity.
The derivative formulas for \(\Phi_f\) are correct: its first derivative is the tilted mean, and its second derivative is the tilted variance. Thus the displayed Hessian satisfies \(\nabla^2J(\theta)\succeq(1/\sigma^2)I\), because all masses are positive.
The lower bound \(\Phi_f(x)-r_tx\geq-\log K\) follows from the exponential term indexed by the actual report value \(r_t\in S_K\). Consequently, the coercivity bound is valid. Continuity and coercivity give existence; strong convexity gives uniqueness.
The cited paper does establish strong convexity in its finite-comparison setting. The prover independently verifies the required property for rational masses, so no extension of the paper’s theorem is being assumed. [Proposition 2](https://arxiv.org/html/2308.08644v2)
Symmetry gives \(\Phi_f'(0)=0\), and the triangle inequality gives \(\|\nabla J(0)\|_2\leq\sqrt2N\). The strong-monotonicity inequality has the correct sign and yields \(\|\theta^*\|_2\leq\sqrt2\,\sigma^2N\). The zero-minimizer case is explicitly covered.
Since \(\sqrt2<2\) and \(\sigma^2N>0\), the claimed strict margin \(\|\theta^*\|_2<R-1\) holds.
The gradient bound on \(D\) is valid: each report contributes at most \(2\sqrt2N\mu_t\) in norm, and \(2\sqrt2<3\). Integrating along segments within the convex ball \(D\) therefore gives the stated Lipschitz inequality. The strong-convexity conversion from objective error to Euclidean error is also correct.
The normalization by \(h=|x|\) is correct for both signs of \(x\). The endpoint term is exactly one, so \(Z\geq1\); no potentially tiny denominator occurs.
For nonnegative integer precision \(p\), the cutoff \(u\geq p+2\) makes returning zero sufficiently accurate. In the remaining case, the stated Taylor remainder bound is valid, and a term count proportional to \(p+1\) with the displayed constant suffices. Exact rational arithmetic accommodates the cancellation in this Taylor expansion without invalidating the bit-complexity bound.
The quotient-error bound \(2K\zeta\) and logarithm-error bound \(K\zeta\) are correct. The preceding clipping to \([0,1]\), together with retaining the endpoint exactly, also ensures \(\widetilde Z\in[1,K]\), as required by the logarithm routine.
The logarithm series converges geometrically at a rate bounded away from one for fixed \(K\). Thus its term count and rational intermediate bit lengths are polynomial in the requested precision and argument bit length.
The objective-error contribution is at most \(Na\), and the gradient-error contribution is at most \(\sqrt2Nb\). Both bounds correctly use \(\sum_t\mu_t=1\), rather than expanding the support into voters.
Accordingly, multiplication by the binary integer \(N\) requires additional precision proportional to its bit length. The quadratic and report-linear contributions are rational and can be computed exactly.
These observations support the stated objective-and-gradient oracle, including when score differences have exponentially large numerical magnitude.
The dimension restriction is satisfied because \(m\geq2\). The update requires a nonzero normal, and the algorithm handles a zero approximate gradient before invoking it.
The transformed half-ball calculation correctly proves containment. Its final expression is at most one because \(t(t+1)\leq0\) on \([-1,0]\).
The determinant gives the stated volume ratio. The logarithmic series has the correct coefficients and sign, yielding \(\log q_n\leq-1/(2n)\).
The lower bound \(B\succeq A/4\) is valid for all \(n\geq2\). Since \(R\geq1\), the induction giving \(\lambda_{\min}(A_i)\geq4^{-i}\) is valid throughout the prescribed budget.
The center-rounding error is sufficiently small in the \(B^{-1}\) norm. The inflation to \(C=(1+\alpha)^2B\) therefore preserves containment.
Symmetric entrywise rounding has operator-norm error at most \(nh\). Adding \(nhI\) gives the claimed lower matrix bound, while the chosen upper bound on \(h\) gives \(\widehat A\preceq(1+\alpha)C\). Positive definiteness is preserved.
The resulting volume inflation is at most \((1+\alpha)^{3n/2}\). With the specified \(\alpha\), the rounded update still contracts volume by at least the claimed factor.
The maximum-eigenvalue bound is also valid. The normalized center displacement is controlled by the current largest semiaxis, so a very small nonzero cut normal does not cause uncontrolled center growth. Once the grid has polynomial bit length, the remaining arithmetic and square-root approximation claims are routine polynomial-bit computations.
Issue 1 — minor: grid precision is insufficiently specified.
Where: Section 3, “Choose a dyadic number \(h\) satisfying …,” followed by “The grid denominator has \(O(T+\log n)\) bits.”
Problem: The upper bound on \(h\) does not imply the asserted bound on its denominator. Arbitrarily smaller dyadic numbers also satisfy that inequality. For sufficiently large \(T\), a choice such as \(h=2^{-2^T}\) satisfies the upper bound while requiring exponentially many denominator bits.
Minimum clarification: Specify a deterministic choice of \(h\) whose dyadic denominator exponent is \(O(T+\log n)\), in addition to satisfying the displayed inequality. This is a routine parameter-selection clarification, not a missing optimization lemma.
All accuracy parameters are positive rationals of polynomial bit length. The strict radius margin and \(\rho\leq1\) place the entire ball \(P\) inside \(D\). Its objective values are within \(\Delta/4\) of the minimum.
An outside-domain cut retains all of \(D\), with the displayed strict inequality having the correct sign.
If \(g=0\), the true gradient norm is at most \(\eta\). The convexity inequality then bounds the objective gap by \(2R\eta=\Delta/4\), sufficiently small for the requested approximation.
For an evaluated center with gap greater than \(\Delta\), convexity gives a true-gradient separation margin greater than \(3\Delta/4\). Approximation consumes at most \(\Delta/4\), leaving a strictly separating cut that retains every point of \(P\).
Therefore, if every evaluated center were bad, every update would retain \(P\). The specified iteration count makes the final ellipsoid volume strictly smaller than the volume of \(P\), a contradiction. This argument correctly requires preservation of \(P\) only under the hypothesis that all evaluated centers are bad.
Issue 2 — minor: the iteration parameter needs a bounded selection rule.
Where: Section 4, the choice of an integer \(b\geq1\) satisfying \(R/\rho\leq2^b\), and the subsequent assertion that \(b\) and \(T\) are polynomially bounded.
Problem: The inequality alone allows arbitrarily large \(b\). Polynomial bit length of \(R/\rho\) ensures that a suitable polynomially bounded \(b\) exists; it does not bound every permitted choice.
Minimum clarification: Specify a deterministic choice of \(b\) bounded by a polynomial in the bit length of \(R/\rho\). No new mathematical estimate is required.
At least one center is recorded because the initial center is zero. Selecting the smallest approximate objective value incurs at most \(2\nu\) additional objective error. Thus the output gap is at most \(3\Delta/2\).
The final calculation is correct: strong convexity bounds the squared distance by \(3\sigma^2\Delta=(3/4)\varepsilon_0^2\leq\varepsilon^2\).
The construction outputs a rational vector. It covers \(\varepsilon>1\), isolated alternatives, zero report values when present in \(S_K\), and the zero minimizer. Each listed mass contributes once; no reversal or duplication assumption enters the argument.
The two issues are expositional choices affecting the literal complexity specification. The substantive proof establishes polynomial-time approximation once those routine choices are made explicit.
⟨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.