| paper | d4-conf-aaai-2016-0558 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 1 has computational character: it gives explicit strategies minimizing information leakage. But the proposed population model produces exactly the paper’s existing \(P\sim\mathrm{Bernoulli}(p)\) mixture for a sampled advisor, and the paper already optimizes over that same mixture; the mirror is already distributional rather than a new population question.
fails bit b-already — the paper is already native to the continuum
The paper already models advisor honesty as \(P\sim\mathrm{Bernoulli}(p)\), so treating \(p\) as honest-advisor mass makes the proposed problem distributionally identical to Corollary 1.
fatal: True
The proposed question covers Corollary 1’s blind-user attack optimization; it leaves the paper’s aware-user and general-user results and other analyses aside.
The strongest honest positive case is a narrow mirror of the paper’s attack-optimization problem. There is no numbered result here that classifies a problem as polynomial-time, NP-hard, or otherwise by computational complexity. The best anchor is an exact optimization result instead.
Anchor: Corollary 1, stated in this paper. Its proof combines this paper’s Theorem 2 with Theorems 3 and 4 of Wang et al. (2015a), so the argument relies partly on cited prior results. For blind users, zero information leakage is possible exactly when \(0\le p\le \tfrac12\) and every history-dependent attack probability satisfies \(a_b=\frac{1-2p}{2-2p}\). When \(\tfrac12\le p\le1\), leakage is minimized by setting \(a_b=0\) for every history. At \(p=\tfrac12\), both prescriptions give the same strategy.
A continuous-population version would model a large trust platform with two advisor types: honest advisors of mass \(p\), and coordinated attackers of mass \(1-p\). For example, these could be accounts following one platform-standard honest process and accounts running the same attack script. There may be millions of advisors but only these two types, so \(\tau=2\). A user selects an advisor without knowing its type and receives ratings about \(n\) targets. The target observations \(O_i\) are independent fair bits, as in the paper’s maximum-uncertainty assumption. An honest advisor reports \(O_i\). The attacker chooses a policy \(a=(a_b)\), where \(b\in\{0,1\}^{<n}\) records whether its earlier ratings matched its observations, and \(a_b\) is the probability that its next rating matches.
This gives a precise problem: given \(n\) and a rational mass \(p\), choose the attackers’ common policy \(a_b\in[0,1]\) to minimize the blind user’s total per-round information leakage, \(\mathcal L_n=\sum_{i=1}^n\bigl(H(O_i\mid R_{<i})-H(O_i\mid R_{\le i})\bigr)\). The solution is a minimizing policy and its leakage value. Corollary 1 supplies the policy directly: for \(p\le\tfrac12\), use the same \(a_b=\frac{1-2p}{2(1-p)}\) at every history; for \(p\ge\tfrac12\), always lie, so \(a_b=0\). The minimum is \(0\) in the first range and \(n(1-h_2(p))\) in the second, where \(h_2\) is binary entropy. I expect this mirror to be tractable: the optimal policy has a compact closed-form description, even though an unrestricted policy has exponentially many history states. That tractability is my inference from the corollary, not a complexity claim made by the paper.
This mirror covers the paper’s optimization of attacks against blind users, and keeps the rounds, observations, and ratings discrete. The continuous object is the advisor population: \(p\) is the mass of honest advisors, rather than an integer count. A natural next question is whether the same compact optimization survives with \(\tau>2\) advisor types, such as several distinct attack scripts, or with users who have limited auditing accuracy.
The soft spot is substantial: the paper already represents honesty with a random variable whose probability is \(p\). Interpreting that probability as a population mass may therefore be a restatement of its existing model, not a genuinely new continuous-population question. The paper also does not provide a computational-complexity result for this optimization. So this is a plausible, tightly scoped high-multiplicity reading of a named result, but not a strong claim that the paper opens a new complexity landscape.
The paper has no named result about the computational complexity of an input problem. Its numbered results derive leakage formulas and characterize optimal attack probabilities. Corollary 1 is the proponent’s strongest anchor, but its proposed population model is already represented in the paper.
The honesty variable \(P\) is a fixed advisor type across all \(n\) rounds, with \(\Pr(P=1)=p\). If a user samples an advisor uniformly from a platform with honest mass \(p\) and attacker mass \(1-p\), that sampling produces exactly the paper’s distribution over \(P\). The joint law of \(P\), the observations, the ratings, and the user’s information is unchanged. In particular, Theorem 2 makes the blind-user leakage independent of past ratings, and Corollary 1 directly characterizes the optimal policy from that mixture. A finite platform with \(k\) honest advisors out of \(N\) gives \(p=k/N\); the paper already allows \(p\) to vary over \([0,1]\). Reading \(p\) as population mass therefore adds no new computational question.
A stronger proposal might give advisors \(\tau>2\) types, each with a different attack script. If a user samples one advisor, those masses form a richer prior over the latent advisor type. Searching over scripts or adding constraints on their use could produce a new optimization problem, but its extra difficulty comes from heterogeneous policies or campaign constraints, not from replacing headcounts with mass. If instead users aggregate ratings from many advisors, the information target changes from one advisor’s observations to some population-level quantity. That could be a worthwhile trust-security question, but it would not mirror Corollary 1. The same limitation applies to the aware-user and general-user results: their population interpretation of \(p\) is already present in the model.
So the negative case is strongest for this one anchor: its proposed two-type mirror is a population reading of an existing latent-type distribution. I cannot rule out a useful new model with cross-advisor aggregation or constrained attacker populations, but those would need their own motivation and results; this paper does not supply a continuous-complexity gap for them.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.