| paper | d4-conf-wine-2024-0020 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\). Every accepted family has a successful ordering constructible in time polynomial in \(m,\tau,L,d,N(k)\) and the bit length of \(k\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a fixed finite set of network roles \(T\), a fixed signal accuracy \(q\), a role-incidence rule generating graphs \(G_N\), and rational role distributions \(\mu^{(N)}\) with \(N\mu_t^{(N)}\in\mathbb{Z}_{\ge 0}\), determine whether there is an ordering family \(\sigma_N\) for which Bayesian network learning quality \(L_{\sigma_N}(G_N)\to 1\), and construct such a family when it exists. In particular, characterize the hub-and-seed regime with a hub \(v_N\), an independent neighbor set \(S_N\), \(|S_N|\to\infty\), \(|S_N|/N\to0\), and a component containing all but \(o(N)\) agents after removing \(S_N\).
A sequence of high-multiplicity societies described by role distributions \(\mu^{(N)}\), together with a role-incidence rule that specifies the social network. The decision variable is an ordering of the agents generated by those role counts, and the objective is the average Bayesian probability of a correct prediction.
The mirror covers Theorem 3’s sufficient condition and its constructed ordering for Bayesian learning. It leaves aside the other graph-family results, random-order bounds, majority-rule simulations, and the conjecture about NP-hardness.
There is no anchor that meets your stated rule. Theorem 1 and Theorem 2 classify learning behavior for particular graph families and orderings; Theorem 3 gives a sufficient condition for successful learning; Theorems 5 and 6 establish success for preferential attachment and grid graphs. None asserts a computational complexity classification such as polynomial time, NP-hardness, or fixed-parameter tractability. The paper’s conclusion says that finding an ordering is *conjectured* NP-hard, but that conjecture is neither proved nor a numbered result. I can’t present it as an anchor.
The strongest nearby result is Theorem 3, proved in this paper. It says: for a family of graphs, if each graph has a vertex \(v\) with an independent set \(S\) of neighbors such that \(|S|=\omega(1)\), \(|S|=o(n)\), and after removing \(S\), the component containing \(v\) includes all but \(o(n)\) of the remaining vertices, then some decision ordering achieves network-wide asymptotic truth learning under the Bayesian model. The construction orders \(S\) first, lets \(v\) aggregate their signals, then traverses the component to propagate the accurate decision.
That suggests a narrow, plausible unanchored lead: *Role-Template Bayesian Learning-Order Design*. Take a fixed finite set of network roles \(T\), a symmetric contact template describing which roles connect, a fixed signal accuracy \(q\), and a sequence of rational role masses \(\mu^{(N)}\), with \(N\mu_t^{(N)}\) agents of each role. In the graph formed by those roles and contacts, ask whether there is a sequence of decision orderings \(\sigma_N\) for which the Bayesian network learning rate satisfies \(L_{\sigma_N}(G_N)\to1\). A solution is an explicit ordering family; a negative answer is a proof that no such family reaches learning rate \(1\). For a hub, seed, and bulk template, the theorem’s conditions give a positive case when the seed count diverges but its population fraction vanishes, and the hub remains connected to all but a vanishing fraction of the population.
A plausible regime would be a large organization or platform with many exchangeable pilot users, a small number of aggregation roles, and a much larger group that can observe the resulting decisions. The appeal is that the ordering problem remains the authors’ Bayesian learning problem, while the input describes proportions across roles. But the proposed problem asks about structured network families, not a complexity result proved by this paper. The theorem supplies a sufficient condition for one part of it; it does not classify the general ordering problem.
The weakness is substantial: the seed must have \(o(n)\) population mass while still containing \(\omega(1)\) agents. A fixed limiting distribution \(\mu\) forgets that absolute count, so the mirror needs a population scale or a sequence of distributions. Also, representing a general graph with a small number of complete agent types is often implausible: network position may be part of an agent’s complete type, causing the number of types to grow with the population. So there is a credible high-multiplicity scenario behind Theorem 3, but under your anchor rule this paper supplies no qualifying result to anchor a continuous complexity question to.
The strongest objection is that this paper supplies no proved computational result to mirror. Theorems 1–6 classify asymptotic learning behavior for graph families and orderings; Theorem 3 gives a sufficient structural condition for an ordering to work. The paper’s claim that finding such an ordering is NP-hard is only a conjecture. Turning these results into complexity questions about continuous populations would therefore introduce a new problem, rather than continuize a computational result the paper establishes.
Theorem 3 is still the best candidate for a mirror, and the proposed hub–seed–bulk setting is plausible. A hub can aggregate signals from \(s_n\) independent neighbors and pass its decision to most of the population, with \(s_n\to\infty\) but \(s_n/n\to0\). That is a real high-multiplicity regime; dismissing it on the ground that agents cannot repeat would be wrong.
Its success does, however, depend on a scale that a fixed limiting distribution over roles loses. The seed’s share vanishes even as its absolute size grows, and the hub’s share vanishes too. Keep the population size and the shrinking role masses so the mechanism remains visible, and the proposed object is a sequence of finite learning networks. Replace that with a fixed atomless continuum, and a positive-mass seed contains effectively unlimited independent signals, so the finite-count threshold and its sublinear-versus-linear tradeoff disappear. The theorem’s key phenomenon is precisely the intermediate scale between a finite group and a positive fraction of society.
A block or role model could preserve that scale by specifying a population-size sequence, the network incidences between roles, and an ordering. But then role masses alone do not determine what agents observe or what the Bayesian updates are; the network topology remains essential input. Such a project may be worthwhile, but it is a new computational problem about ordering structured networks, not a continuous mirror of a proved complexity result in this paper. The theorem certifies some successful regimes; it does not establish an algorithmic classification for that problem.
So I would reject the proposed lead as an anchor under the programme’s stated rule. I would not claim the broader negative is airtight: a scale-aware, high-multiplicity study of learning orders could be sensible. The case against is strongest as a judgment about this paper’s fit for the programme, and weaker as a claim that no useful continuous follow-up exists.
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.