| paper | d4-conf-ijcai-2019-0952 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Solvable in deterministic time polynomial in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given \(m\) candidates and an explicit rational distribution \(\mu\) over complete rankings, promised to equal the uniform distribution \(U(T)\) over rankings single-peaked on a unique labeled tree \(T\), output \(T\).
Each complete ranking \(v\) is a voter type with mass \(\mu_v\); the population distribution is promised to be \(U(T)\), and the task is to recover the unique generating tree \(T\) from the listed types and masses.
The exact distribution reveals the full support, so this mirror does not preserve the finite-sample uncertainty or sample-complexity content of Theorem 10; the proponent acknowledges this, and the finite-sample bridge connects only the target tree.
fatal: False
The mirror covers Theorem 10's high-probability tree-recovery objective in the full-population limit. It does not mirror Theorem 7's finite-sample certainty lower bound, the sampling algorithms, or the empirical experiments.
The strongest honest case is an exact population limit of the paper’s tree-learning problem.
My anchor is Theorem 10, proved in this paper. For any tree \(T\) with \(m\) vertices and any \(\delta>0\), Algorithm 5 receives \(2m\alpha\) independent votes drawn uniformly from the rankings single-peaked on \(T\). If \(\alpha\ge 2\log m+\log(1/\delta)\), the algorithm returns \(T\) with probability at least \(1-\delta\). Thus the paper gives a high-probability recovery guarantee using \(O(m(\log m+\log(1/\delta)))\) votes. The paper has no named P, NP-hardness, or parameterized-complexity theorem for tree identification; Theorem 10 is its closest named computational anchor, as an algorithmic sample-complexity result.
The continuous mirror I would put to a prover is Exact Mass Tree Identification. An instance gives \(m\ge3\) candidates and an explicit distribution \(\mu\) over complete rankings, with binary-rational masses summing to one. It is promised that \(\mu\) is exactly \(U(T)\) for a unique labeled tree \(T\): every ranking single-peaked on \(T\) has mass \(1/|\mathcal S(T)|\), and every other ranking has mass zero, where \(\mathcal S(T)\) is the set of rankings single-peaked on \(T\). The task is to output that tree. A solution is a tree whose single-peaked rankings are exactly the support of \(\mu\). Each ranking is a voter type, and \(\mu_v\) is the fraction of society with type \(v\).
This is a population continuization because the paper’s sampling law becomes the society’s type proportions themselves. A plausible regime is a large electorate ranking a fixed, moderate set of alternatives: the electorate is much larger than the number \(\tau=|\mathcal S(T)|\) of distinct ranking types, so many voters share each type. The paper’s uniformity assumption is stylized, but the target remains the same: recover the unknown tree that generates single-peaked preferences.
I expect this exact problem to be tractable in time polynomial in \(m,\tau,L\), where \(L\) is the mass bit length. The full support reveals every allowed ranking, so the paper’s attachment-digraph construction can be applied to the support to recover the unique suitable tree. Theorem 10 provides the finite-sample bridge: it shows that the same underlying tree can already be recovered with high probability from a relatively small random profile. This mirror covers the paper’s tree-recovery question; it does not turn its finite-sample certainty lower bound into a continuous hardness claim.
The follow-up question is how recovery changes when the supplied masses are noisy or estimated from a finite electorate. For example, given arbitrary rational \(\mu\), one could ask for a tree whose uniform single-peaked law is closest to \(\mu\), under a specified distance measure.
The weak point is that exact population masses give the learner more information than the paper’s sampled votes, and the support can be large as \(m\) grows. The continuous problem may therefore reduce to ordinary tree recognition over an explicitly listed set of rankings. Theorem 10 supports the connection to the authors’ problem, but it does not establish that this exact-mass version is a new or difficult computational problem.
Theorem 10 is the one serious anchor, but it gives a sample-complexity guarantee: how many random votes are needed to identify a latent tree with high probability. Its bound is \(2m\alpha\) votes for \(\alpha \ge 2\log m+\log(1/\delta)\). It does not give a complexity boundary for a computation on a society supplied as type masses.
The proposed exact-mass mirror changes the information available. If the input is \(\mu=U(T)\), every single-peaked ranking has positive mass, so the support reveals the entire domain. The path lower bound in Theorem 7 illustrates what disappears: finite samples may miss two rare rankings needed for certain identification, while an explicit \(\mu\) lists those rankings regardless of how small their masses are. Tree recovery then depends on the support, not the masses; the paper’s attachment-digraph method and the cited tree-recognition algorithms apply to that support. This is a coherent population question, but it does not carry over Theorem 10’s central challenge.
The strongest alternative would allow a misspecified or contaminated population and ask for a tree maximizing the mass of compatible rankings, or minimizing a distance from \(\mu\) to \(U(T)\). That could be worthwhile, but it needs choices the paper does not make: a loss or distance, a contamination model, and conditions under which a tree is identifiable. Those choices define a new robust distribution-learning problem. If instead \(\mu\) is estimated from observed voters, the finite sample remains the source of uncertainty, and the task returns to the paper’s sampling model.
So the negative case rests on a mismatch of objects: exact population masses remove the sampling problem; noisy masses require a new problem specification. That defeats the proponent’s exact-mass anchor as a mirror of Theorem 10. The case is not airtight, though: the paper’s latent-tree model could inspire a useful continuous robustness study if its authors accepted those added assumptions.
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.