| paper | d4-conf-ijcai-2015-0682 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Proposition 3 has computational character: it gives a construction that reduces the snapshot joins needed by the paper’s estimator. But the proposed continuous question replaces the observed graph and its subgraph joins with a random network specified by type-level contact rates, so it does not preserve the problem that Proposition 3 addresses.
fails bit b-changes — the continuum limit changes the question
The type-level contact kernel discards the specific shared-node and shared-edge structure on which Proposition 3's join-independence guarantee depends.
fatal: True
The proposed model captures the broad IC spread-estimation objective, but mirrors none of the paper's graph-specific incremental results; Proposition 3's snapshot-join guarantee is left out.
The strongest positive case is narrow: make the population continuous while keeping the paper’s IC influence-spread objective. Imagine a large marketing network made up of recurring customer or community cohorts. A type records an agent’s network role and contact rates with every other type; agents of the same type are interchangeable for the model. The mass \(\mu_t\) is the fraction of the population in type \(t\). With millions of agents and a modest number \(\tau\) of such roles, choosing a fraction of each type to seed is more natural than choosing named individuals one at a time.
The closest named anchor is Proposition 3, proved in this paper. It says that one can select \(M\) groups \(T_\beta\) that are pairwise join-independent. Each group averages \(M\) snapshot joins, giving an estimator based on \(M^2\) joins rather than enumerating all \(M^N\) combinations across \(N\) subgraphs. The paper gives an alternating-index construction for those joins. This is a real algorithmic result about estimating expected spread, but it does not assert that a problem is in P, NP-hard, or in another complexity class. The paper’s Theorem 1 is Hoeffding’s inequality, cited from elsewhere. Its NP-hardness and #P-hardness statements appear in prose with citations, not as numbered results. So Proposition 3 is the best available anchor for a positive case, but it does not meet the assignment’s strict complexity-anchor criterion.
My lead candidate is Typed-Mass IC Spread Estimation. An instance gives a finite type set \(T\), rational masses \(\mu_t\) summing to one, rational symmetric contact intensities \(\lambda_{tu}\), seed masses \(a_t\in[0,\mu_t]\), and accuracy parameters \(\varepsilon,\delta>0\). For each sufficiently large \(n\) divisible by the input denominators, form a network with \(n\mu_t\) agents of type \(t\); each pair of types \(t,u\) has an independently live edge with probability \(\lambda_{tu}/n\). Seed \(na_t\) agents of each type. Let \(F(\mu,\lambda,a)\) be the limit, as \(n\) grows, of the expected fraction of agents reachable from those seeds. The task is to output a rational \(\widehat F\) such that
\[
\Pr\!\left[|\widehat F-F(\mu,\lambda,a)|\le\varepsilon\right]\ge 1-\delta,
\]
in time polynomial in \(\tau\), the input bit length, \(1/\varepsilon\), and \(\log(1/\delta)\), with no dependence on \(n\).
This mirrors the paper’s spread-estimation problem, the computation Proposition 3 supports; it does not claim the proposition itself carries over to the continuum. I would expect a Class A answer at least when \(\tau\) is fixed: the sparse, finite-type model suggests a description through multitype branching and reachability equations. Whether a robust polynomial algorithm extends to variable \(\tau\), especially near critical contact rates, is a natural further question. A companion problem is to choose seed masses under a total budget \(b\), maximizing \(F\); then one could ask whether the paper’s greedy approximation guarantee has a continuous counterpart.
The mirror covers expected influence spread and its use in seed selection. It does not cover the paper’s arbitrary observed graph or its incremental subgraph-joining method. That is the weakest point: Proposition 3 saves work by reusing and joining finite random snapshots, whereas the proposed mirror changes the network model to a finite-type population kernel. An author could reasonably accept the IC spread objective as the same underlying problem while rejecting this as a direct mirror of the paper’s technical contribution. And although viral marketing involves selecting agents, it is adjacent to ChoCo rather than a standard social-choice problem about collective decisions.
The paper offers no numbered complexity result for a continuous mirror to carry over. Its NP-hardness and \(\#\)P-hardness statements are background claims with citations; Theorem 1 is Hoeffding’s inequality. The closest in-paper anchor is Proposition 3, which bounds the number of snapshot-join groups used by this particular estimator. That is a real algorithmic claim, but it is not a complexity classification of influence estimation or maximization.
Proposition 3 depends on the paper’s concrete input: a fixed graph split into edge-disjoint subgraphs, individual snapshots on each subgraph, and joins whose SCC structure depends on the identities of shared nodes and edges. A mass distribution over types and a matrix of type-to-type contact rates do not retain that information. To preserve the original graph’s topology in the types, one may need nearly one type per node, losing the aggregation. Coarse types avoid that blow-up by replacing the observed graph with a stochastic, exchangeable network. That gives a sensible multitype diffusion question, but it no longer mirrors the streaming snapshot-join result or its technical problem.
The stronger version—optimize seed masses under a per-capita budget in a sparse finite-type contact model—could be worthwhile in its own right. But it changes both the network input and the seed decision: the paper takes an observed graph and chooses \(k\) particular nodes, while this model supplies a random contact law and chooses fractions of types. The nearby “continuous influence maximization” literature also varies discounts for users on a fixed graph; that is continuous campaign action, not a continuous population ([AAAI 2020](https://ojs.aaai.org/index.php/AAAI/article/view/5332)). These are adjacent questions, not evidence that this paper’s result has a continuous mirror.
So the strongest negative case is that no type construction preserves the paper’s distinctive result: exact topology keeps the population individualized, while a tractable type kernel replaces the paper’s problem with another one. The case is weakest if ChoCo is willing to treat finite-type random-network influence maximization as an acceptable adjacent problem; that is a plausible research question, but it does not rescue the proposed anchor to Proposition 3.
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.