| paper | d4-conf-atal-2020-0287 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: Yes. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
For each sufficiently large \(k\), does there exist a finite catalogue \(\mathcal H\) of equal-size \(n\) undirected linear-threshold community templates and rational community masses \(\mu_H\), with \(\sum_H\mu_H=1\), such that assigning each community \(k\) seeds by template-wise greedy yields aggregate infected-mass ratio at most \(1-(1-1/k)^k+Ck^{-1/5}\) relative to the best template-wise \(k\)-seed assignments, for some constant \(C\)?
Use a society of repeated, independent communities: each template \(H\in\mathcal H\) has \(n\) vertices and paper-defined influence \(\sigma_H(S)\); \(\mu_H\) is its fraction of communities. Let \(x_{H,S}\) be the fraction assigned local seed set \(S\), with \(\sum_{|S|=k}x_{H,S}=\mu_H\). The infected population fraction is \(\mathrm{Inf}(x)=\frac{1}{n}\sum_{H,S}x_{H,S}\sigma_H(S)\); compare template-wise greedy assignments with assignments maximizing this quantity.
Mass is assigned to whole community templates, so the local graph structure and seed choices remain finite and the anchored bounds lift by replication or averaging; this limits the mirror to repeated-community societies rather than continuizing the network interactions themselves.
fatal: False
The mirror covers Theorem 3.2’s upper bound on greedy’s approximation ratio and, as a companion, Theorem 4.1’s lower guarantee. It leaves the directed, weighted, prescribed-seed, and edge-weighted variants, as well as the paper’s conjecture and cited hardness results, outside the mirror.
The strongest mirror I believe in is a population of repeated local networks. It keeps the paper’s cascade dynamics intact while making the population itself continuous.
Take a finite catalogue \(\mathcal H\) of equal-size, undirected community templates. A template \(H\) has \(n\) vertices and runs the paper’s linear threshold model internally. Let \(\mu_H\) be the fraction of communities using template \(H\), with \(\sum_H\mu_H=1\). The society consists of a continuum of copies of these communities. An individual’s type is their role in a template: people in the same role have the same degree and the same pattern of contacts within their community. With \(M\) copies, there are \(Mn\) people but only the template’s role types; \(M\) can grow while the number of types stays fixed. This fits settings such as a platform with many local groups drawn from a small catalogue of recurring network structures.
Give each community \(k\) seed placements. Let \(x_{H,S}\) be the fraction of communities of type \(H\) assigned local seed set \(S\), where \(|S|=k\) and \(\sum_{|S|=k}x_{H,S}=\mu_H\). If \(\sigma_H(S)\) is the paper’s expected number infected in \(H\), the population fraction infected is
\[
\mathrm{Inf}(x)=\frac{1}{n}\sum_H\sum_{|S|=k}x_{H,S}\sigma_H(S).
\]
Thus the action is a mass allocation over local campaign plans, and the objective is infected population mass. The greedy policy assigns each community type’s mass to the seed set produced by running the paper’s greedy algorithm on that template; the optimum assigns it to a best local seed set.
My lead is Theorem 3.2, proved in this paper. It states that for every sufficiently large \(k\), there is an instance of influence maximization on an undirected graph under the paper’s linear threshold model where greedy achieves at most a \((1-(1-1/k)^k+O(k^{-0.2}))\)-approximation.
The corresponding continuous question, Cohort-LT-Greedy-Upper\(_k\), is: given \(k\), a catalogue of templates, and rational community masses, does there exist a continuous society whose greedy policy has ratio at most \(1-(1-1/k)^k+Ck^{-1/5}\), for some constant \(C\)? A solution is a template family, masses, and greedy and optimal policies witnessing that ratio. I expect yes: put all mass on the graph family from Example 3.3 and replicate it across communities. Its local influence values and greedy choices are unchanged, so the aggregate ratio is the same. The example’s many repeated clique and star roles also make a large population with relatively few types plausible.
The companion anchor is Theorem 4.1, also proved here. It states that on every undirected graph under the same model, greedy achieves at least a \((1-(1-1/k)^k+\Omega(1/k^3))\)-approximation; the improvement is independent of graph size. The matching continuous question, Cohort-LT-Greedy-Lower\(_k\), asks whether every typed society in this model satisfies that same aggregate ratio. I expect yes: apply the theorem to each template, multiply by its mass, and sum. This is a finite-\(k\) structural guarantee, not a claim that exact influence maximization is tractable.
For the exact optimization problem generated by this mirror, I would expect Class B: each local template retains its network combinatorics, so high multiplicity across communities does not remove the hard part of choosing seeds within a community. The paper’s NP-hardness and \(\#\)P-hardness claims appear in prose as results cited from other work, rather than as numbered computational theorems here, so I would not use them as anchors. The two numbered results above are the paper’s strongest named results for this case.
This mirror covers the paper’s greedy approximation results, not all of its settings. It also suggests a further question: with a single seed budget shared across community types, can one optimize the mass allocation over local seed plans efficiently, or does the pricing problem retain the local hardness?
The weakest point is that continuity lies across communities, while each community keeps a finite graph and discrete seed placements. A referee might see this as a high-multiplicity wrapper around the original problem, and the paper gives each graph one global seed budget rather than a per-community quota. The case survives because the quota is a natural per-capita supply in repeated-community settings, and the population-level mass objective is genuinely continuous. The mirror preserves the local cascade—including its finite network structure—while asking how the guarantee behaves for an aggregate society.
The two proposed cohort questions are true mirrors in the narrow algebraic sense, but they do not yet pose computational problems about a continuous population. In the upper-bound question, set all community mass on the graph from Example 3.3. Theorem 3.2 already supplies the witness; replication changes no greedy choice or influence value. In the lower-bound question, apply Theorem 4.1 to each template and sum the inequalities weighted by community mass. The result follows immediately. Neither question asks for an algorithm, a complexity classification, or a new optimization over the mass distribution.
The model also locates the mass on whole communities. A community template records who is connected to whom, and the mass variables record how many copies receive each local seed plan. If types instead describe individual roles, their marginal masses do not encode which roles share a community or how they are connected. Keeping that information requires carrying the community template alongside the type distribution. With a fixed \(k\)-seed quota per community, the continuum then allocates fractions of communities among finite plans; the cascade and its combinatorics remain inside each finite graph.
A shared seed budget across communities is the stronger version. It gives a real allocation problem over plans, but its influence values still come from finite templates. If the communities are independent, the construction is a disjoint union of those graphs. If fractions of communities can receive each plan, the objective and budget constraints form a linear optimization over plan frequencies; the hard part is generating useful local plans, which is the original influence-maximization problem. That could be a reasonable high-multiplicity optimization problem, but it does not make the population continuum do computational work in the paper’s greedy analysis.
An individual-level limit would need a relational model, such as a population of types plus an interaction structure. That raises a substantial modelling issue for this paper’s linear-threshold process: a fixed number \(k\) of seeds has zero population mass in the limit, while the paper’s results depend on finite paths and individual neighbors. Scaling the seed budget to a positive mass may produce an interesting problem, but it changes the parameter and diffusion regime behind Theorems 3.2 and 4.1. Those theorems would not anchor the resulting complexity questions without a new bridge.
So the strongest objection is that the proponent’s anchors either lift the paper’s finite-graph results by averaging, or require a different network-limit model whose computational questions the paper does not establish. I cannot make that a universal case against every plausible scenario. Repeated autonomous communities are credible, and a shared-budget high-multiplicity formulation could be useful in its own right. The negative case is strongest against these particular anchors as evidence for ChoCo’s continuous-population complexity programme; it is weaker against the broader possibility of a worthwhile network continuization.
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.