Answer: Both guarantees are achievable in \(\operatorname{poly}(m,\tau,L,\log N)\) time for every fixed \(\xi>0\).
Theorem 5.1 — class: algorithmic
Given \(m\) candidates and a society \(\mu\) supported on \(\tau\) rankings, with binary rational masses satisfying \(N\mu_\pi\in\mathbb{Z}_{\ge 0}\), find a randomized mechanism outputting a ranking \(\psi\) that is \((\varepsilon,\delta)\)-DP when one person changes type, corresponding to moving mass \(1/N\) between rankings. Can it guarantee \(\mathbb{E}[K_\mu(\psi)]\le (1+\xi)\operatorname{OPT}_K(\mu)+\widetilde O_{\xi,\delta}\!\left(\frac{m^{65/22}\sqrt{\log(1/\delta)}}{\varepsilon N}\right)\), with runtime polynomial in \(m,\tau,L,\log N\), where \(K_\mu(\psi)=\sum_\pi\mu_\pi K(\psi,\pi)\)? The pure-DP version asks for additive error \(\widetilde O_\xi\!\left(\frac{m^{27/7}}{\varepsilon N}\right)\).
Let \(m,N\ge 1\) be integers, with \(N\) public and encoded in binary; types and outputs are strict rankings in \(S_m\).
A society is given by its support: the list of its \(\tau\) rankings with positive binary rational masses \(\mu_\pi\), satisfying \(\sum_\pi\mu_\pi=1\) and \(N\mu_\pi\in\mathbb Z_{\ge0}\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length.
Write \(K\) for Kendall's tau distance, \(K_\mu(\psi)=\sum_\pi\mu_\pi K(\psi,\pi)\), and \(\operatorname{OPT}_K(\mu)=\min_{\psi\in S_m}K_\mu(\psi)\).
Use central differential privacy with public binary rational parameters \(0<\varepsilon\le1\) and \(0<\delta<1/2\). Neighboring societies have the same \(N\) and differ by transferring mass \(1/N\) from one ranking to another; the transfer may change the support. Pure privacy uses \(\delta=0\).
Fix any constant \(\xi>0\). The notation \(\widetilde O_\xi\) suppresses constants depending on \(\xi\) and polylogarithmic factors in \(m,N,1/\varepsilon,1/\delta\), omitting \(1/\delta\) in the pure case.
Can a randomized mechanism running in \(\operatorname{poly}(m,\tau,L,\log N)\) time guarantee, on every such society,
\(\mathbb E[K_\mu(\psi)]\le(1+\xi)\operatorname{OPT}_K(\mu)+\widetilde O_\xi\!\left(\frac{m^{65/22}\sqrt{\log(1/\delta)}}{\varepsilon N}\right)\) under \((\varepsilon,\delta)\)-DP,
and, separately, \(\mathbb E[K_\mu(\psi)]\le(1+\xi)\operatorname{OPT}_K(\mu)+\widetilde O_\xi\!\left(\frac{m^{27/7}}{\varepsilon N}\right)\) under pure \(\varepsilon\)-DP, or is either approximation guarantee computationally unattainable in this runtime?
For an explicit list of \(N\) rankings, [Hillebrand et al.](https://arxiv.org/html/2511.11319v1) establish both guarantees in \((Nm)^{O(1)}\) time for every fixed \(\xi>0\).
No result establishing or excluding these guarantees with the stated support-encoded runtime was located.
Both guarantees are achievable in the stated support-encoded runtime.
The key is to use the explicit-list theorem only when the *effective population* \(\varepsilon N\) is polynomially bounded. In that regime, sampling and privacy amplification reduce the input to a polynomial-size explicit list. For larger \(\varepsilon N\), a mechanism operating directly on pairwise comparison counts suffices.
The proof below also accounts for finite-bit sampling and exact pure privacy.
Fix \(\xi>0\). Write
\(\displaystyle D=\binom m2,\qquad t=\varepsilon N.\)
The case \(m=1\) is immediate, so assume \(m\ge2\). All Kendall costs lie in \([0,D]\).
For distinct candidates \(u,v\), define the integer count
\(\displaystyle c_{uv}=N\sum_\pi\mu_\pi\mathbf1[\pi(u)<\pi(v)]\)
and put \(w_{uv}=c_{uv}/N\). These counts can be computed exactly from the support in polynomial time. They satisfy \(c_{uv}+c_{vu}=N\), and a neighboring transfer changes each count by at most one.
For a weight matrix \(A\), use the convention
\(\displaystyle \operatorname{cost}_A(\psi)=\sum_{\psi(u)<\psi(v)}A_{vu}.\)
Thus \(K_\mu(\psi)=\operatorname{cost}_w(\psi)\).
We use two established results:
\(\displaystyle A_{uv}\ge0,\qquad \tfrac12\le A_{uv}+A_{vu}\le2,\)
it returns a ranking of cost at most \((1+\xi)\min_\psi\operatorname{cost}_A(\psi)\), in polynomial time for fixed \(\xi\). Scaling \(A\) by \(1/2\) gives the hypotheses of the [Kenyon-Mathieu–Schudy weighted-tournament PTAS](https://cs.brown.edu/~claire/Publis/kenyonschudy.pdf).
Let an explicit-list mechanism on \(n\) records be \((\varepsilon_0,\delta_0)\)-DP. Uniformly sample \(n\le N\) distinct labeled individuals, put them in uniformly random order, and apply that mechanism.
The resulting mechanism is
\(\displaystyle \left(\log\!\left(1+\frac nN(e^{\varepsilon_0}-1)\right),\frac nN\delta_0\right)\text{-DP}.\)
Here is a proof under the replacement adjacency required in the question.
Let neighboring populations differ only at one labeled individual, whose record is respectively \(a\) or \(b\). Put \(q=n/N\). When \(n<N\), let \(Q\) be the output law conditional on excluding that individual, and let \(P_a,P_b\) be the laws conditional on including it.
The conditional samples defining \(P_a,P_b\) can be coupled to differ in one coordinate. Likewise, \(P_a\) and \(Q\) can be coupled by replacing the included record \(a\) with a uniformly selected unused unchanged record. Consequently, for every output event, writing \(u=Q(E)\), \(v=P_a(E)\), \(z=P_b(E)\),
\(\displaystyle v\le e^{\varepsilon_0}\min(u,z)+\delta_0.\)
It follows that
\(\displaystyle v-z\le(e^{\varepsilon_0}-1)\min(u,z)+\delta_0.\)
Since \(\min(u,z)\le(1-q)u+qz\), the unconditional laws satisfy
\(\displaystyle
(1-q)u+qv
\le
\bigl(1+q(e^{\varepsilon_0}-1)\bigr)\bigl((1-q)u+qz\bigr)+q\delta_0.
\)
Interchanging the populations proves the reverse inequality. If \(n=N\), coupling their uniformly random orderings directly gives the original privacy guarantee.
The labeled population is only a proof device: sampling can be implemented from the integer support multiplicities.
Let \(\widehat\mu\) be the empirical society of a uniform sample without replacement of size \(n\), and define
\(\displaystyle
\Delta=\max_{\psi\in S_m}|K_{\widehat\mu}(\psi)-K_\mu(\psi)|.
\)
For each unordered pair, the empirical comparison frequency has variance
\(\displaystyle
\frac{p(1-p)}n\frac{N-n}{N-1}\le\frac1{4n}
\)
when \(N>1\). Every ranking selects one comparison cost per unordered pair. Therefore
\(\displaystyle
\Delta\le\sum_{u<v}|\widehat w_{uv}-w_{uv}|,
\qquad
\mathbb E\Delta\le\frac D{2\sqrt n}.
\)
When \(n=N\), \(\Delta=0\).
If \(\psi^\ast\) optimizes the original society, then
\(\displaystyle
\mathbb E[\operatorname{OPT}_K(\widehat\mu)]
\le
\mathbb E[K_{\widehat\mu}(\psi^\ast)]
=
\operatorname{OPT}_K(\mu).
\)
Hence an explicit-list mechanism with expected guarantee
\(\displaystyle
\mathbb E[K_{\widehat\mu}(\psi)\mid\widehat\mu]
\le(1+\xi)\operatorname{OPT}_K(\widehat\mu)+\beta
\)
gives
\(\displaystyle
\mathbb E[K_\mu(\psi)]
\le(1+\xi)\operatorname{OPT}_K(\mu)+\beta+\mathbb E\Delta.
\)
This bound allows the output to depend arbitrarily on the sampled society.
Let \(H\) be the public integer
\(\displaystyle
H=
1+\lceil\log_2(m+1)\rceil+\lceil\log_2(N+1)\rceil
+\lceil\log_2(1/\varepsilon)\rceil,
\)
with \(\lceil\log_2(1/\delta)\rceil\) added in the approximate-private case.
Choose a sufficiently large universal constant \(C\), and put
\(\displaystyle
T=Cm^2H^2,\qquad s=\left\lceil m^4(T+1)^2\right\rceil.
\)
If \(t<1\), output a fixed ranking. Its cost is at most \(D\), which is absorbed by either requested additive bound.
Suppose now that \(1\le t\le T\). Set
\(\displaystyle
n=\min(N,s),\qquad \varepsilon_0=\frac{t}{16n}.
\)
Sample \(n\) distinct individuals in uniformly random order and run the appropriate explicit-list mechanism with parameter \(\varepsilon_0\). For approximate privacy, use \(\delta_0=\delta/16\).
The hypotheses of the explicit-list theorem hold: the sample is an explicit list of strict rankings, and \(\varepsilon_0\le1\). Indeed, if \(n=N\), then \(\varepsilon_0=\varepsilon/16\); otherwise \(n=s\ge T\ge t\).
Using \(e^x-1\le2x\) for \(0\le x\le1\), amplification gives privacy parameter at most
\(\displaystyle
\frac nN\,2\varepsilon_0=\frac{\varepsilon}{8}.
\)
The approximate privacy parameter is at most \(\delta/16\).
Crucially,
\(\displaystyle \varepsilon_0n=\frac{\varepsilon N}{16}.\)
The explicit-list additive bounds therefore become precisely the requested bounds, up to permitted constants and logarithmic factors.
All transformed logarithms are permitted: \(n\le s\), and
\(\displaystyle \varepsilon_0^{-1}\le16s\)
because \(t\ge1\). Moreover, \(\log(1/\delta_0)=O(\log(1/\delta))\).
The extra sampling error is zero if \(N\le s\). Otherwise,
\(\displaystyle
\mathbb E\Delta\le\frac D{2\sqrt s}\le1.
\)
This constant is absorbed by the requested additive terms: for either exponent \(p\in\{65/22,27/7\}\), the condition \(t\le Cm^2H^2\) implies
\(\displaystyle
1=O\!\left(\frac{m^pH^2}{t}\right).
\)
Finally, the sample size and \(\varepsilon_0^{-1}\) are polynomial in \(m,H\). Thus this branch runs in polynomial time in the original input length, including even a polynomial dependence on \(\varepsilon_0^{-1}\) in the explicit-list implementation.
Assume \(t>T\). We construct mechanisms using only the counts \(c_{uv}\).
For every \(u<v\), privately release a noisy estimate \(h_{uv}\) of \(w_{uv}\), using independent noise.
Classify the pair as follows:
Use fresh independent noise for a second release:
If \(A\) satisfies the bounded-tournament conditions from Section 1, run the deterministic PTAS on \(A\). Otherwise output a fixed ranking.
All classifications and the boundedness test are post-processing of private releases.
Put
\(\displaystyle a=\frac{\varepsilon}{32D},\qquad r=1-a.\)
At both stages, add independent integer noise \(Z\) with probability mass function
\(\displaystyle
\Pr(Z=k)=\frac{1-r}{1+r}r^{|k|},\qquad k\in\mathbb Z,
\)
to the corresponding integer count, then divide by \(N\).
The first vector of integer queries has \(\ell_1\)-sensitivity at most \(D\). Conditional on any first-stage classification, the second vector has \(\ell_1\)-sensitivity at most \(2D\).
A translation by an integer vector \(h\) changes the joint noise likelihood by at most \(r^{-\|h\|_1}\). Since
\(\displaystyle \log(1/r)\le2a,\)
the first release is \(\varepsilon/16\)-DP and the second is \(\varepsilon/8\)-DP. Adaptive composition gives privacy at most \(3\varepsilon/16\).
For each integer count query, add an independent Gaussian with standard deviation
\(\displaystyle
\sigma_c=\frac{16\sqrt D}{\varepsilon}
\sqrt{2\log(20/\delta)},
\)
then round the released count to the nearest integer and divide by \(N\).
The first query vector has \(\ell_2\)-sensitivity at most \(\sqrt D\), and the second has sensitivity at most \(2\sqrt D\), uniformly over first-stage classifications.
The Gaussian mechanism therefore makes each stage \((\varepsilon/8,\delta/16)\)-DP. Rounding is post-processing. The composed mechanism is \((\varepsilon/4,\delta/8)\)-DP.
Let \(\mathcal E\) be the event that every normalized noise at both stages has magnitude at most \(1/32\).
On \(\mathcal E\), a strongly oriented pair satisfies
\(\displaystyle w_{uv}>27/32,\)
so its nonzero noisy weight lies between \(21/32\) and \(33/32\). A balanced pair satisfies
\(\displaystyle 3/32\le w_{uv}\le29/32,\)
so both noisy opposite weights lie between \(1/16\) and \(15/16\), and sum to one.
Thus \(A\) is a bounded nonnegative tournament on \(\mathcal E\).
For geometric noise,
\(\displaystyle
\Pr(\mathcal E^c)
\le6D\exp\!\left(-\frac{t}{1024D}\right).
\)
For rounded Gaussian noise, Gaussian tails give, for a universal positive constant \(c\),
\(\displaystyle
\Pr(\mathcal E^c)
\le4D\exp\!\left(-\frac{ct^2}{m^2H}\right).
\)
Here the rounding error is at most \(1/(2N)\), and \(N\ge t>T\) is sufficiently large.
Because \(H\ge\log_2N\) and \(t>Cm^2H^2\), choosing \(C\) sufficiently large makes both bounds at most \(1/N\).
Condition on the first-stage classification. Define \(W^0\) by retaining the true weights on balanced pairs and replacing each strongly oriented pair \((u,v)\) by
\(\displaystyle W^0_{uv}=w_{uv}-w_{vu},\qquad W^0_{vu}=0.\)
Also put
\(\displaystyle B=\sum_{\text{strong }(u,v)}w_{vu}\ge0.\)
For every ranking,
\(\displaystyle
K_\mu(\psi)=B+\operatorname{cost}_{W^0}(\psi).
\)
This is an exact pair-by-pair identity.
Let
\(\displaystyle
\Gamma=\max_{\psi\in S_m}
|\operatorname{cost}_A(\psi)-\operatorname{cost}_{W^0}(\psi)|.
\)
On \(\mathcal E\), the PTAS guarantee and the preceding identity imply
\(\displaystyle
K_\mu(\psi)
\le(1+\xi)\operatorname{OPT}_K(\mu)+(2+\xi)\Gamma.
\)
Indeed, applying the PTAS comparison to an original optimum introduces two objective perturbations; the remaining constant term is \(-\xi B\le0\).
On \(\mathcal E^c\), cost is at most \(D\). Consequently,
\(\displaystyle
\mathbb E[K_\mu(\psi)]
\le(1+\xi)\operatorname{OPT}_K(\mu)
+(2+\xi)\mathbb E\Gamma+\frac DN.
\)
It remains to bound \(\mathbb E\Gamma\).
For Gaussian noise, each fixed ranking’s unrounded perturbation is a sum of at most \(D\) independent signed Gaussians. A Gaussian maximum bound over the \(2m!\) signed objective perturbations, together with rounding error, gives
\(\displaystyle
\mathbb E\Gamma
\le\frac{\sigma_c}{N}\sqrt{2D\log(2m!)}+\frac D{2N}
=
O\!\left(
\frac{m^{5/2}\sqrt{\log(m+1)\log(1/\delta)}}{t}
+\frac{m^2}{N}
\right).
\)
For completeness, geometric noise admits an analogous maximum bound. Its moment generating function is
\(\displaystyle
\mathbb E e^{zZ}
=
\frac{a^2}{a^2-2r(\cosh z-1)}.
\)
For \(|z|\le a/4\), using \(\cosh z-1\le z^2\) yields
\(\displaystyle
\log\mathbb E e^{zZ}\le\frac{4z^2}{a^2}.
\)
Conditional on classification, a ranking’s perturbation has coefficients in \(\{0,1,-1\}\). Hence, for \(0<\lambda\le aN/4\),
\(\displaystyle
\mathbb E\Gamma
\le
\frac{\log(2m!)}{\lambda}
+\frac{4D\lambda}{a^2N^2}.
\)
Optimizing within this interval gives
\(\displaystyle
\mathbb E\Gamma
=
O\!\left(
\frac{\sqrt{D\log(2m!)}+\log(2m!)}{aN}
\right)
=
O\!\left(\frac{m^{7/2}\log(m+1)}{t}\right).
\)
Thus the large-population branch has additive errors
\(\displaystyle
\widetilde O_\xi\!\left(
\frac{m^{5/2}\sqrt{\log(1/\delta)}}{\varepsilon N}
\right)
\quad\text{and}\quad
\widetilde O_\xi\!\left(
\frac{m^{7/2}}{\varepsilon N}
\right).
\)
They are stronger than the requested errors because \(5/2<65/22\) and \(7/2<27/7\).
The preceding ideal mechanisms leave privacy slack. We now use that slack to obtain bounded polynomial running time without assuming exact continuous sampling or unbounded rejection sampling.
Maintain the remaining integer multiplicities. At each step, select an integer in the interval of remaining population labels and locate its support block.
A uniform integer in an interval of size \(M\le N\) can be approximated by taking a uniform \(b\)-bit integer modulo \(M\). Its total variation error is at most \(M/2^b\).
Thus an entire ordered sample of size at most \(s\) can be approximated within total variation \(\eta\), with
\(\displaystyle b=O(\log N+\log s+\log(1/\eta))\)
bits per step. No expansion of the population occurs.
The geometric and rounded Gaussian distributions can likewise be approximated within any prescribed total variation error \(\eta\) in time polynomial in their parameter bit lengths and \(\log(1/\eta)\).
To see the relevant complexity, truncate their integer support to \([-R,R]\) with omitted probability at most \(\eta/4\). Their tail bounds allow \(\log R\) to be polynomially bounded in the parameter bit lengths and \(\log(1/\eta)\).
Use inverse-CDF sampling on a sufficiently fine dyadic uniform grid, evaluating the CDF to error \(O(\eta/R)\). Binary search takes \(O(\log R)\) evaluations. Errors can affect the coupled inverse samples only when the uniform value lies near one of the \(2R+1\) CDF boundaries; the total probability of those intervals is \(O(\eta)\). Geometric CDFs use rational powers, and Gaussian CDFs admit polynomial-time numerical evaluation to the required precision.
Allocate the error across the \(2D\) draws. This produces a mechanism \(Q_\mu\) whose output law is within total variation \(\eta\) of the ideal law \(P_\mu\), uniformly over societies. Actual released matrices are rational and have polynomial bit length.
Choose
\(\displaystyle \eta\le\min(\delta/100,1/N).\)
The ideal mechanism has privacy at most \((\varepsilon/4,\delta/8)\). For every output event,
\(\displaystyle
Q_\mu(E)
\le e^{\varepsilon/4}Q_{\mu'}(E)
+\delta/8+(1+e^{\varepsilon/4})\eta
\le e^\varepsilon Q_{\mu'}(E)+\delta.
\)
The expected cost increases by at most \(D\eta\le D/N\).
Total variation approximation alone would not preserve pure privacy. Use the following explicit repair.
Put \(F=m!\). Construct a data-independent distribution \(U\) on rankings satisfying
\(\displaystyle U(\psi)\ge\frac1{2F}\)
for every ranking: take a uniform sufficiently long bit string, reduce its integer value modulo \(F\), and unrank the resulting permutation.
Set
\(\displaystyle
\lambda=2^{-\lceil\log_2N\rceil},
\qquad
\eta\le\frac{\varepsilon}{100NF},
\qquad
R_\mu=(1-\lambda)Q_\mu+\lambda U.
\)
The mixture probability \(\lambda\) is dyadic and can be implemented exactly. Also
\(\displaystyle \frac1{2N}\le\lambda\le\frac1N.\)
The ideal mechanism is at most \(\varepsilon/4\)-DP, so
\(\displaystyle
Q_\mu(E)
\le e^{\varepsilon/4}Q_{\mu'}(E)
+(1+e^{\varepsilon/4})\eta.
\)
For every nonempty event \(E\), \(U(E)\ge1/(2F)\). Since \(e^\varepsilon-1\ge\varepsilon\),
\(\displaystyle
(1+e^{\varepsilon/4})\eta
\le(e^\varepsilon-1)\lambda U(E).
\)
Substituting into the mixture inequality gives
\(\displaystyle R_\mu(E)\le e^\varepsilon R_{\mu'}(E).\)
The empty event is immediate. Thus \(R\) is exactly pure \(\varepsilon\)-DP.
The repair increases expected cost by at most
\(\displaystyle D\eta+\lambda D=O(D/N).\)
Its precision requirement remains polynomial because
\(\displaystyle
\log(1/\eta)=O(\log N+\log(1/\varepsilon)+m\log(m+1)).
\)
Only a permutation index is computed; the \(F\) rankings are never enumerated.
Every branch is selected using public parameters.
The sample branch processes at most \(s=\operatorname{poly}(m,H)\) rankings and invokes the given explicit-list theorem with \(\varepsilon_0^{-1}\le16s\). The large branch computes \(D\) pairwise counts directly from the support and runs a PTAS on a rational matrix of polynomial bit length. The finite-bit implementations and privacy repair also take polynomial time.
Since \(H\) is bounded by the public input bit length, the total runtime is
\(\displaystyle \operatorname{poly}(m,\tau,L,\log N)\)
for each fixed \(\xi\).
The sampling error, numerical approximation error, and privacy-repair cost are all absorbed by the permitted logarithmic factors. Therefore, on every valid society, the resulting mechanisms satisfy respectively
\(\displaystyle
\mathbb E[K_\mu(\psi)]
\le
(1+\xi)\operatorname{OPT}_K(\mu)
+\widetilde O_\xi\!\left(
\frac{m^{65/22}\sqrt{\log(1/\delta)}}{\varepsilon N}
\right)
\)
under \((\varepsilon,\delta)\)-DP, and
\(\displaystyle
\mathbb E[K_\mu(\psi)]
\le
(1+\xi)\operatorname{OPT}_K(\mu)
+\widetilde O_\xi\!\left(
\frac{m^{27/7}}{\varepsilon N}
\right)
\)
under pure \(\varepsilon\)-DP.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and establishes both requested guarantees, subject to minor implementation clarifications. I found no false central step or gap requiring new mathematics.
The sampling reduction addresses the dependence on the binary population size, and the large-population mechanism achieves the claimed stronger additive bounds. The exact pure-privacy repair is valid. The remaining issues concern the choice of numerical precision and the specification of numerical routines.
The pairwise counts are integers because every support multiplicity \(N\mu_\pi\) is integral. They can be computed from the support using polynomially many operations on integers of polynomial bit length. A neighboring transfer changes each selected comparison count by at most one.
The cost convention is consistent: a ranking placing \(u\) before \(v\) incurs disagreement weight \(w_{vu}\). Thus the displayed identity between Kendall cost and tournament cost is correct.
The explicit-list result has the expected-cost interpretation and replacement adjacency required here. Its stated additive exponents agree with the prover’s invocation. I treat the explicit-list polynomial-time mechanisms as the premise supplied by USER_TASK; their internal proofs need not be reproved in this audit. [Hillebrand et al., Definition 1.1 and Theorem 5.1](https://arxiv.org/html/2511.11319v1)
The weighted-tournament PTAS applies to nonnegative weights with opposite-edge sums bounded above and below by positive constants. Scaling the prover’s matrix by one half gives opposite-edge sums in \([1/4,1]\), satisfying the cited formulation with a fixed lower-bound constant. The source explicitly permits derandomization in polynomial time for fixed approximation accuracy. Consequently, the deterministic PTAS invocation is justified. [Kenyon-Mathieu–Schudy, Problem 2 and Theorem 1](https://cs.brown.edu/~claire/Publis/kenyonschudy.pdf)
The cases \(m=1\) and \(t<1\) are handled correctly. In the latter case, the requested additive allowance absorbs the maximum cost \(D\).
The amplification proof is valid for replacement adjacency.
The conditional inclusion laws can be coupled to differ in one coordinate. The coupling between inclusion and exclusion also works: replacing the included changed individual by a uniformly selected unused unchanged individual produces the required exclusion sample distribution, including its uniformly random ordering.
Both applications of privacy therefore justify
\(v\le e^{\varepsilon_0}\min(u,z)+\delta_0\).
The subsequent inequality for \(v-z\) is correct because \(\min(u,z)\le z\). The comparison
\(\min(u,z)\le(1-q)u+qz\)
is also correct. These inequalities yield exactly the stated amplified parameters.
The proof separately handles \(n=N\), avoiding an undefined exclusion law. It also covers \(n=1\) and \(N=1\) through the stated branches.
The finite-population variance formula is correct for \(N>1\). Each ranking’s objective difference is bounded by the sum of absolute empirical comparison errors, so
\(\mathbb E\Delta\le D/(2\sqrt n)\)
follows.
The expected empirical optimum is bounded by evaluating the empirical objective at a fixed original optimum. This correctly gives
\(\mathbb E[\operatorname{OPT}_K(\widehat\mu)]\le\operatorname{OPT}_K(\mu)\).
The transfer of the sampled mechanism’s guarantee is valid even though its output depends on the sample: the definition of \(\Delta\) provides a simultaneous bound over all rankings.
There is no missing independence assumption here.
The choices of \(T\) and \(s\) are polynomial in \(m\) and the public input length.
The privacy parameter satisfies \(\varepsilon_0\le1\) in both cases:
The amplification calculation correctly gives privacy at most \(\varepsilon/8\), and approximate privacy at most \(\delta/16\).
The identity \(\varepsilon_0n=t/16\) transfers the explicit-list additive bounds with only permitted constant and logarithmic changes. The transformed inverse privacy parameter is polynomially bounded because \(t\ge1\).
When sampling occurs, the extra expected error is at most one. Its absorption is justified by \(t\le Cm^2H^2\) and both requested exponents being greater than two.
Thus this branch establishes the required accuracy and support-encoded runtime, using the explicit-list mechanism granted in the task.
For a fixed first-stage classification, the second-stage queries are well-defined integer queries:
Their stated sensitivities are correct. Adaptive composition is legitimate because the second-stage sensitivity bounds hold uniformly for every fixed classification.
For geometric noise, the likelihood-ratio bound and
\(\log(1/r)\le2a\)
give the stated stage privacy parameters. Their sum is \(3\varepsilon/16\).
For Gaussian noise, the stated scale meets the standard sufficient Gaussian-mechanism bound for sensitivity \(2\sqrt D\), privacy parameter \(\varepsilon/8\), and failure parameter \(\delta/16\). It therefore also suffices for the first stage. Rounding is post-processing.
The boundedness test and PTAS output depend only on private releases, so they introduce no additional privacy loss.
The interval calculations are correct.
On \(\mathcal E\), a strong orientation has true forward weight greater than \(27/32\). Its noisy difference weight lies in the claimed interval from \(21/32\) to \(33/32\).
For a balanced pair, its true comparison weight lies between \(3/32\) and \(29/32\). Both released opposite weights then lie between \(1/16\) and \(15/16\), and their sum is exactly one.
Therefore the PTAS hypotheses hold on \(\mathcal E\).
The geometric tail estimate is conservative but valid. The rounded-Gaussian estimate has the correct dependence on \(t\), \(m\), and \(H\); the rounding error is negligible under the stated large-population threshold.
The conclusion that both failure probabilities are at most \(1/N\) follows for a sufficiently large universal \(C\). The inclusion of \(\log N\) in \(H\) is essential and is present.
The identity
\(K_\mu(\psi)=B+\operatorname{cost}_{W^0}(\psi)\)
is correct for both possible orders of each strong pair.
The perturbation comparison correctly produces the coefficient \(2+\xi\). The constant contribution is \(-\xi B\), which is nonpositive. The argument does not require \(W^0\) to be nonnegative outside \(\mathcal E\).
The treatment of the failure event is valid: the output always has Kendall cost at most \(D\), giving an additional expected contribution at most \(D/N\).
Conditioning on the first-stage classification preserves independence of the fresh second-stage noise. The Gaussian maximum calculation consequently has the stated variance bound and yields the claimed \(m^{5/2}\) dependence, with the displayed logarithmic and rounding terms.
The geometric moment-generating function is correct. Its restricted quadratic bound is valid, and the constrained optimization gives the stated two-term maximum bound. The simplification to
\(O(m^{7/2}\log(m+1)/t)\)
is a valid upper bound.
Finally,
\(5/2<65/22\)
and
\(7/2<27/7\).
The large-population errors therefore fit within the requested allowances.
The modulo construction for support sampling has the stated total variation bound. Accumulating the error over polynomially many draws is legitimate and does not require expanding the population.
The truncated inverse-CDF construction is valid in substance. Its boundary argument requires a sufficiently fine dyadic grid and CDF evaluations with certified error; the stated precision scales permit polynomial bit length.
Minor issue 1 — numerical routines are underspecified.
The sentence “Geometric CDFs use rational powers, and Gaussian CDFs admit polynomial-time numerical evaluation to the required precision” does not specify the bit complexity or certified error contract of those routines.
Exact evaluation of a rational power with an exponentially large exponent can itself produce exponentially many bits. Thus “rational powers” alone is not an adequate implementation specification. The intended bounded-precision evaluation is routine, but should be stated.
Minimum clarification: specify or cite certified bounded-precision CDF evaluation routines whose time is polynomial in the parameter encoding length, \(\log R\), and \(\log(R/\eta)\), including how the nonrational Gaussian scale is evaluated. No change to the mechanism or mathematical estimates is required.
The elementary sampling and noise approximations then yield the claimed uniform total variation approximation. Integer translations and subsequent post-processing preserve the coupling bound.
The approximate-privacy transfer inequality is correct. The available slack absorbs
\((1+e^{\varepsilon/4})\eta\),
and bounded cost gives the stated utility loss.
The pure-privacy repair is also correct:
The mixture calculation legitimately uses \(e^\varepsilon-1\): the data-independent component supplies that amount of slack, while the data-dependent component already has privacy parameter at most \(\varepsilon/4\).
Minor issue 2 — the precision bound does not follow from the stated inequality alone.
The condition
\(\eta\le\varepsilon/(100NF)\)
does not imply the later upper bound on \(\log(1/\eta)\). An arbitrarily smaller choice of \(\eta\) would satisfy the condition while requiring arbitrarily more precision. The same specification issue occurs in the approximate-private choice.
Minimum clarification: choose an explicit dyadic tolerance within a fixed constant factor of each displayed upper bound. This makes the asserted precision and runtime bounds verifiable without altering any privacy or utility calculation.
All branch decisions use public parameters. The support computation, polynomial-size sampling, rational matrix processing, and permutation indexing have the claimed polynomial size.
The additive sampling, failure, numerical, and mixture costs are all absorbed by the requested allowances. The proof uses support size rather than the total number of possible rankings and accommodates support-changing neighbors.
Accordingly, the argument resolves both guarantees in substance. It provides no evidence of computational unattainability. The two implementation clarifications above are expositional and do not require new mathematics.
⟨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.