ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let p∈[0,1]p\in[0,1] be the bias parameter, let cc be the collusion size, and let Pr⁡[Y=1∣P=p]\Pr[Y=1\mid P=p] denote the output-one probability under the worst collusion attack. For the Tardos pdf

f(p)=p(1−p)π,f(p)=\frac{\sqrt{p(1-p)}}{\pi},

define

qconv(p)=2arcsin⁡(p)π.q^{\mathrm{conv}}(p)=\frac{2\arcsin(\sqrt{p})}{\pi}.

Tardos worst-attack convergence conjecture. As the collusion size increases, the worst collusion attack makes Pr⁡[Y=1∣P=p]\Pr[Y=1\mid P=p] converge to qconv(p)q^{\mathrm{conv}}(p). More specifically, Pr⁡[Y=1∣P=p]\Pr[Y=1\mid P=p] is the orthogonal projection of qconv(p)q^{\mathrm{conv}}(p) onto the affine subspace spanned by the Bernstein polynomials {Pr⁡[Σ=σ∣P=p]}σ∈[c−1]\{\Pr[\Sigma=\sigma\mid P=p]\}_{\sigma\in[c-1]} and containing the polynomial Pr⁡[Σ=c∣P=p]\Pr[\Sigma=c\mid P=p]; equivalently,

∫01(Pr⁡[Y=1∣P=p]−qconv(p))Pr⁡[Σ=σ∣P=p]고 dp=0,∀σ∈[c−1].\int_0^1\bigl(\Pr[Y=1\mid P=p]-q^{\mathrm{conv}}(p)\bigr)\Pr[\Sigma=\sigma\mid P=p]고\,dp=0,\qquad \forall\sigma\in[c-1].

The claim is presented as a conjecture inferred from numerical optimization, with no formal proof supplied in the paper.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.