| paper | d4-conf-aaai-2014-0262 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 5 gives upper and lower bounds on a combinatorial count, not a computational result under the stated criteria. The proponent acknowledges that no numbered computational result anchors the proposed finite-sample likelihood question, so it cannot pass the required gate.
fails bit a — no named computational result to mirror
The proposed mirror concerns Theorem 5's bounds on \(a(n,m,\mathrm{SP})\); it leaves the paper's other counting and deletion results without a proposed computational mirror.
The strongest honest positive case is narrow, and it does not meet your anchor rule in its strict complexity-theoretic sense. The paper has named counting theorems, but no numbered result classifying a problem as polynomial-time, NP-hard, or similar. Its closing NP-completeness statement about CONFIGURATION CONTAINMENT is unnumbered, described as preliminary, and has no proof here. I would not use it as an anchor.
The nearest named anchor is Theorem 5, proved in this paper. For \(n,m\ge2\), it bounds the number \(a(n,m,\mathrm{SP})\) of single-peaked \((n,m)\)-profiles by
\[
\frac{m!}{2}\,2^{(m-1)n}\bigl(1-\varepsilon(n,m)\bigr)
\le a(n,m,\mathrm{SP}) \le
\frac{m!}{2}\,2^{(m-1)n},
\]
where, for each fixed \(m\), \(\varepsilon(n,m)\to0\) as \(n\to\infty\). Dividing by \((m!)^n\) gives the corresponding Impartial Culture likelihood. This is a named and substantive counting result, but it is not a complexity classification.
A plausible continuous question anchored to it is Single-Peaked Sample Likelihood from a Continuous Electorate. The instance is a candidate set \(C\), a finite support \(T\subseteq S_m\) of \(\tau\) complete rankings, binary-rational masses \(\mu_t>0\) summing to \(1\), and a sample size \(n\). The mass \(\mu_t\) is the fraction of a large electorate with ranking \(t\). Draw \(n\) voters independently from that electorate and return the exact probability that their profile is single-peaked with respect to some common axis. For uniform \(\mu\), Theorem 5 gives bounds on this probability; arbitrary \(\mu\) is the continuous-population extension. A setting with \(n\gg\tau\)—for example, a large public consultation with many people sharing a comparatively small set of complete rankings—makes the high-multiplicity interpretation credible.
I expect this likelihood problem to be FPT in \(\tau\), though polynomial time in \(\tau\) is open. For any subset \(S\subseteq T\), the probability that the sample’s support is exactly \(S\) is
\[
\sum_{U\subseteq S}(-1)^{|S|-|U|}\mu(U)^n,
\qquad
\mu(U)=\sum_{t\in U}\mu_t.
\]
Summing this over the subsets \(S\) whose rankings form a single-peaked profile gives an exact algorithm using \(2^{O(\tau)}\) terms, with single-peaked recognition for each subset. The solution is the resulting rational probability; a threshold version could instead ask whether it is at least a specified rational \(q\). This covers the paper’s single-peaked likelihood result, not its single-crossing, 2D single-peaked, deletion-distance, or local-candidate-deletion results.
The weakest point is also the decisive one: the query still concerns a finite sample. Its defense is that the electorate supplied to the problem is itself the continuous object \(\mu\), while the sample is the observed profile whose likelihood is being assessed. If the sample is treated as the society and \(\mu\) merely as a noise model, this falls outside the programme’s scope. And even if accepted, it does not test whether a discrete hardness result dissolves under continuization: Theorem 5 is a counting bound, not a hardness anchor.
The strongest case against the proposed anchor is that Theorem 5 is a counting theorem, not a computational result. It bounds how many finite \((n,m)\)-profiles are single-peaked and, after normalization, their likelihood under Impartial Culture. It gives no complexity classification for a computational problem. On the programme’s strict anchor standard, that leaves no named computational result here to continuize.
The proposed sample-likelihood question does not close that gap. Its input is a mass distribution \(\mu\), but its event is still about a finite sample of \(n\) voters. If that sample is the society being assessed, the question is a probability model over discrete profiles, the kind of noise-model continuity the programme distinguishes from continuizing the population. If \(\mu\) itself is the society, then the direct question—whether its positive-mass support is single-peaked—depends only on the support, not the masses. Theorem 5’s count has no direct counterpart there. Putting a probability distribution over possible \(\mu\)'s would require a new choice of prior; ordinary full-support distributions make restricted support an almost-sure impossibility, while sparse-support priors impose their own assumptions.
There is a stronger possible mirror than the one proposed: given \(\mu\), find the least voter mass to remove so the remaining support is single-peaked. For example,
\[
\delta_{\mathrm{SP}}(\mu)
=\min_A\sum_{t:\,t\text{ is not single-peaked with respect to }A}\mu_t .
\]
That is a sensible high-multiplicity optimization problem, and it connects to the paper’s voter-deletion results. But it changes the paper’s question from counting profiles near a restriction to optimizing deletion mass in a supplied society. It may be worth studying on its own; it does not rescue Theorem 5 as a computational anchor. For the likelihood question, retaining the paper’s target brings the finite sample back in.
So the negative case is strong against the proponent’s anchor, but weak against the requested universal claim. The mass-deletion variant is a live candidate a careful reader could accept as a worthwhile mirror of the deletion results. I cannot honestly rule out every scenario; I would reject the proposed likelihood mirror under the programme’s scope and flag the broader negative verdict as uncertain.
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.