| paper | d4-conf-aaai-2020-0878 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: For fixed \(m\ge\nu\ge3\), an unconditional randomized polynomial-time \(\Omega(1/\log n)\) multiplicative approximation is achievable with an explicit dyadic distribution and success probability at least \(2/3\). Thus some nonnegative non-increasing \(g(n)=o(1)\) admits an \(n^{-g(n)}\) approximation, and every fixed \(\epsilon>0\) admits an \(n^{-\epsilon}\) approximation. Both stated universal pooled-budget barriers are overcome. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
Given a finite directed network template \(G=(V,E)\), its campaign cascade distributions and initial seed sets, a threshold \(\nu\), and an average seed budget \(K\), consider a continuum of copies of \(G\). Each copy receives an integral seed plan \(\sigma\), with cost \(c(\sigma)\) and expected balanced-exposure value \(b(\sigma)\). Choose a distribution \(\pi\) over plans maximizing \(\sum_\sigma \pi_\sigma b(\sigma)/|V|\), subject to \(\sum_\sigma\pi_\sigma=1\), \(\sum_\sigma\pi_\sigma c(\sigma)\le K\), and \(\pi_\sigma\ge0\). Determine its approximation complexity, including whether the conditional inapproximability of Theorem 2 persists under this pooled budget.
A continuum of repeated copies of one finite network template, with each role \(v\in V\) carrying mass \(1/|V|\). Each copy receives an integral seed plan; the distribution of plans across copies is the decision variable, and the objective is expected balanced exposure per person under an average seed budget.
The mirror covers Theorem 2's heterogeneous deterministic hardness result; it leaves the paper's approximation algorithms and correlated setting aside.
The lead mirror I would hand to a prover is Replica-Balance. Take one network module \(G=(V,E)\) with the paper’s \(M\) campaigns, initial seed sets \(I_i\), campaign-specific cascade probabilities, and threshold \(\nu\). The society is a continuum of copies of this module, indexed by \(z\in[0,1]\). A type is a role \(v\in V\) within a module, including its cascade connections, initial status, and seed cost. Relabeling the module does not change the type. If \(n=|V|\), each role has mass \(1/n\); with \(q\) actual copies there are \(qn\) people but only \(n\) types.
A seed plan for one module is \(\sigma=(S_i)_{i\in[M]}\), with cost \(c(\sigma)=\sum_i|S_i|\) and value
\[
b(\sigma)=\mathbb{E}_{X}\!\left[\NoSM\bigl(\rho_X(I\cup\sigma)\bigr)\right].
\]
The continuous decision is a distribution \(\pi\) over these plans: mass \(\pi_\sigma\) of the modules gets plan \(\sigma\). Given an average budget \(K\) seed incidences per module, Replica-Balance asks for a feasible distribution maximizing
\[
\frac{1}{n}\sum_\sigma \pi_\sigma b(\sigma),
\qquad
\sum_\sigma\pi_\sigma=1,\quad
\sum_\sigma\pi_\sigma c(\sigma)\le K,\quad
\pi_\sigma\ge0.
\]
Its value is the expected fraction of the population reached by either none or at least \(\nu\) campaigns. Every person still gets an integral seed assignment; the type-level seed masses are fractional because they aggregate across a continuum of modules. A finite society of \(q\) modules gives the corresponding discrete model, with a budget near \(qK\); its empirical distribution over seed plans approximates \(\pi\).
A plausible regime is a very large platform with many repeated local communities—districts, campuses, or branches—with the same communication template and campaign rates. Members in the same role across communities are interchangeable for the model. Here the number of people can grow with the number of communities while the number of types stays at \(n\). This is a population limit: the unit of mass is people in network roles, and the objective remains the paper’s exposure objective. Campaign propagation remains stochastic inside each module.
My anchor is Theorem 2, proved in this paper. It states that for \(d\ge2\), \(\nu\ge d+1\), and \(p=d!/d^d\), approximation for the *deterministic* \(\mathrm{BAL}_{\mu,\nu}\) problem would yield approximation for Densest-\(k\)-Sub-\(d\)-Hypergraph. In the \(d=2\) case, if \(\alpha(n)=n^{-g(n)}\), where \(g\) is non-increasing and \(g(n)=o(1)\), then an \(\alpha(|\overline V|)\)-approximation for deterministic balance yields a \(\beta(|V|)\)-approximation for the hypergraph problem, where
\[
\beta(n)=\frac{p\,n^{-6g(n)}}{2\lambda}.
\]
For \(d\ge3\), if \(\alpha(n)=n^{-\epsilon(d)}\), then it yields \(\beta(n)=p\,n^{-\epsilon'(d)}/(2\lambda)\), with \(\epsilon'(d)=(d+4)\epsilon(d)\). Here \(\lambda=d!\binom{\mu-\nu+d}{d}\), and \(\overline V\) and \(V\) are the constructed balance and source-hypergraph vertex sets. The paper applies known hardness for the source problems to conclude, under Gap-ETH, no \(n^{-g(n)}\)-approximation for \(g(n)=o(1)\) when \(\nu\ge3\), and under its cited one-way-function assumption, no \(n^{-\epsilon}\)-approximation for \(\nu\ge4\), for a constant \(\epsilon>0\) depending on \(\nu\).
Replica-Balance asks whether that hardness persists when the population of network modules is continuous. The theorem’s reduction can serve as a module: it already has the same seed choices, cascade semantics, budget, and balanced-exposure objective. What changes is that the central authority allocates its total budget across a continuum of modules. My provisional expectation is Class B, because the anchor’s combinatorics sits in the network template and its seed choices, not in the number of copies. The continuous formulation also gives a natural configuration LP: seed plans are columns, and pricing asks for a high-value plan at a given seed price.
The anchor does not prove this expected classification. In particular, the average budget lets the continuous society mix plans across modules. That convexification could erase the approximation gap from the fixed-budget reduction; a prover would need to show the gap survives, or find an efficient pricing method. Further questions include whether pricing is hard, whether the hardness bounds survive the mixture, and how much of the balance objective’s approximation behavior is changed by allocating different budgets to different modules.
The weakest point is the regime: many repeated network templates are plausible for local campaign settings, but an arbitrary hypergraph gadget is not thereby a typical social platform. And if repeated modules feel too stylized, this anchor may not persuade the authors that it is *their* most useful continuous version. I still think it is a defensible question because it preserves the underlying seeding-and-exposure problem, makes population mass the continuous object, and makes the loss or survival of the known hardness an explicit mathematical issue. This case covers Theorem 2’s heterogeneous deterministic hardness, not the paper’s approximation algorithms or its correlated setting.
Theorem 2 is the right anchor: it is a genuine computational result. The difficulty is that its computational object is a network with a particular graph structure, and the proposed continuum keeps that structure intact by treating a whole network module as the unit being allocated to.
Mass over node roles alone does not capture the paper’s objective. Whether a node is reached depends on which other roles are seeded and on the paths between them. To preserve that information, Replica-Balance uses whole-module seed plans. With a per-module budget of \(k\), independent identical modules each get the best plan for the original instance; the continuum adds no new optimization. With an average budget, the model instead asks how to distribute a pooled seeding budget across modules. Its LP is over plans, and an optimum for identical modules needs at most two plans. That is a legitimate resource-allocation question, but Theorem 2 does not establish its hardness: a mixture can use plans costing more than \(k\), so the paper’s fixed-budget reduction does not carry over without new analysis.
A continuum of people inside a connected network would be more faithful to the population idea, but it needs a model that preserves graph structure. For the theorem’s hypergraph gadgets, roles and their incidences carry the reduction’s information; collapsing them to type masses loses that information. Keeping it requires a typed network limit whose structure grows with the instance. A dense mean-field limit would change the cascade setting, while preserving sparse paths and incidences requires retaining much of the finite network structure.
So the negative case is that the cleanest mirror continuizes module-level policy allocation, while a more faithful population limit needs substantial new network-limit modeling and does not inherit Theorem 2 automatically. I would not call this decisive. Repeated communities with a shared budget are plausible, and the resulting configuration-pricing question could interest the authors. The honest case against is therefore weak: this anchor supports a possible new model, but the paper alone does not show that it is a compelling continuous-population mirror.
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.