| paper | d4-conf-aaai-2021-2031 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1 (SDP)
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to one, bounded type-specific contact-stub counts, rational transmission probabilities \(w_{tu}\), and rational seed intensities \(\lambda_t\), take populations with type proportions tending to \(\mu\). Pair compatible stubs uniformly, activate each type-\(t\) agent initially with probability \(\lambda_t/n\), and run the Independent Cascade Model with transmission probability \(w_{tu}\) on type-\(t\)-to-type-\(u\) contacts. Compute the exact limiting distribution of the final infected fraction \(\rho_n\), and determine the complexity in \(|T|\), the parameter bit length, and the degree bound.
A continuous society is the type distribution \(\mu\), where each type specifies a complete bounded contact profile, seed intensity, and transmission behavior. Compatible contacts are generated by uniform stub matching, and the decision variable is absent: the computational output is the limiting law of the infected fraction under the stochastic cascade.
The typed ensemble does not retain instance-specific network dependencies or the separate probabilities of finite cascades that SDP computes, restricting the mirror to random locally tree-like regimes.
fatal: False
The mirror covers Theorem 1’s final cascade-size law in bounded-degree typed sparse configuration-model limits; it leaves exact computation on a fixed tree, conditional node activation probabilities, and TDA’s finite-network approximation guarantees aside.
The best anchor is Theorem 1 (SDP), proved in this paper. It gives an exact message-passing algorithm for the final cascade-size distribution of an Independent Cascade Model on a tree. It is algorithmic rather than a named complexity-class theorem: the paper’s separate complexity analysis gives SDP running time \(O(N^2)\). The paper offers no comparable named hardness result, so this is the natural lead.
In full, the theorem passes three distributions from each node to its parent: \(p_{B_n}\), \(p_{A^0_n}\), and \(p_{A^\Sigma_n}\). For a leaf \(n\) with parent \(p\), their nonzero entries are \(p_{B_n}(0)=1-p_n\), \(p_{B_n}(1)=p_n(1-w_{np})\); \(p_{A^0_n}(0)=(1-p_n)(1-w_{pn})\), \(p_{A^0_n}(1)=(1-p_n)w_{pn}+p_n(1-w_{np})\); and \(p_{A^\Sigma_n}(0)=p_{A^0_n}(0)\), \(p_{A^\Sigma_n}(1)=p_{A^0_n}(1)+p_nw_{np}\). For an internal node with children \(c_1,\ldots,c_k\), it first forms \(p_{na}(a)=(1-p_n)(p_{B_{c_1}}*\cdots*p_{B_{c_k}})[a]\), \(p_{la}(a)=(1-p_n)(p_{A^0_{c_1}}*\cdots*p_{A^0_{c_k}})[a]\), and \(p_a(a)=(p_{A^\Sigma_{c_1}}*\cdots*p_{A^\Sigma_{c_k}})[a]-p_{la}(a)\), where \(*\) is convolution. A nonroot node then sends \(p_{A^0_n}(a)=(1-w_{pn})p_{na}(a)+w_{pn}p_{la}(a-1)+(1-w_{np})p_a(a-1)\), \(p_{B_n}(a)=p_{na}(a)+(1-w_{np})p_a(a-1)\), and \(p_{A^\Sigma_n}(a)=p_{A^0_n}(a)+w_{np}p_a(a-1)\). At the root \(r\), the output is \(p_C(a/N)=p_{na}(a)+p_a(a-1)\). Values outside the supported range are zero.
My proposed mirror is Typed Continuum Cascade-Law Computation. An instance has a finite type set \(T\), rational type masses \(\mu_t\) summing to one, a bounded-degree contact specification for each type, rational type-to-type transmission probabilities \(w_{tu}\), and rational seed intensities \(\lambda_t\). Consider populations of size \(n\) with type proportions tending to \(\mu\), whose compatible contact slots are paired uniformly to produce a sparse, locally tree-like network. Each type-\(t\) agent is initially active independently with probability \(\lambda_t/n\); transmissions along type-\(t\)-to-type-\(u\) contacts succeed independently with probability \(w_{tu}\). The question is to compute the limiting law of \(\rho_n\), the final infected fraction, as \(n\) grows. A solution gives that law exactly—for example, as algebraic numbers with enough information to identify the correct roots. In the usual irreducible supercritical regime, the limit has mass at zero and at the positive major-outbreak size; in the subcritical regime it is concentrated at zero.
This is a population-scale version of the paper’s output, not a continuous outcome space: the society is described by fractions of agents in complete types, and the quantity computed is the distribution of the fraction infected. A plausible setting is epidemic planning across many residents grouped by age, occupation, contact degree, susceptibility, and transmission characteristics: millions of agents but comparatively few modeled types. Agents in a type are interchangeable under the contact and cascade model. There is no policy decision or optimization objective in Theorem 1 itself; its computational task is exact inference of the cascade-size law.
I would expect this mirror to be a Class A candidate, because its sparse, locally tree-like limit is described by finite-type branching and fixed-point calculations. The first tractable regime to pursue is bounded degree and fixed \(\tau=|T|\); a uniform polynomial-time result when \(\tau\) is part of the input is a further question, not something this paper establishes. Other follow-ups include the complexity of exact root selection, what additional atoms arise when the type interaction structure is reducible, and how much finite-population cascade information is lost in the limit.
The weak point is the change in network model. The theorem takes a particular finite tree as input; this mirror uses a typed random-network regime and asks about its large-population limit. The paper’s local-tree motivation and exact tree algorithm make that extension recognizable, but Theorem 1 alone does not prove the limiting result, and the mirror discards finite cascades whose mass vanishes. I would therefore defend this as a credible, focused analogue of the tree cascade-law computation—not as a continuous version of all the paper’s results.
Theorem 1 is a genuine computational anchor: it gives an exact algorithm for the cascade-size distribution on a specified tree, with running time analyzed in Section 3.5. So the strongest case against cannot be that the paper has nothing algorithmic to mirror.
The problem is that the proposed mirror changes what the input describes. In SDP, the graph is fixed, and messages combine dependencies along its particular edges. The paper stresses that those dependencies matter: BP’s node marginals miss the positive dependence that shapes the cascade-size distribution. Type proportions and type-to-type transmission rates do not specify those dependencies. To recover them, a type would need to encode enough of each vertex’s network position; on a general input tree, that can make the number of types grow with \(N\), removing the high-multiplicity compression.
The strongest replacement is a finite-type sparse random-network model. That is a sensible epidemic model, but it adds a random graph ensemble and asks for its asymptotic outbreak law rather than SDP’s exact law on a given network. Its scaling also loses much of the paper’s target: fixed positive seeding probabilities tend to wash out randomness in the infected fraction, while \(O(1/n)\) seeding leaves a limit dominated by “no macroscopic outbreak” versus a major outbreak. Finite cascades, which SDP resolves into separate probabilities, collapse into the zero-fraction mass. One could retain both finite outbreak sizes and the macroscopic-outbreak component, but that becomes a branching-process limit problem. Multitype epidemic final-size limits already have a substantial analytic literature, including work on multitype epidemic threshold limits and multitype Reed–Frost processes ([threshold-limit theorem](https://www.sciencedirect.com/science/article/pii/0025556493900142), [asymptotic final-size distribution](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/35811AD583AD4250A6F3ACE464AAFBFB/S0021900200111751a.pdf/asymptotic-final-size-distribution-of-the-multitype-reedfrost-process.pdf)). That is not a computational collision, but it makes the proposed fixed-point computation look more like a new asymptotic epidemic model than a continuation of SDP’s algorithmic problem.
This is a strong objection to the specific mirror, but it does not establish the universal negative. A more elaborate continuum model might preserve local graph structure and still expose a worthwhile computational question; the price is that its type space may cease to be small. I would call the case against credible but limited: it shows that the proponent’s clean finite-type limit does not preserve the paper’s central computational object, rather than proving that no author-recognizable continuous mirror 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.