| paper | d4-conf-sigecom-2012-0028 |
| 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→NP-hard discrete result → its continuous mirror
Answer: NP-hard, even for fixed \(c=2\), fixed \(p=1/4\), uniform dyadic masses, and \(\epsilon=1/(32n)\) in the reduction. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.3
statement extracted from the paper’s text layer
Given a finite set of roles \(T\), rational masses \(\mu_t>0\) summing to \(1\), a symmetric interaction matrix \(A\) with zero diagonal, signal probability \(p\), and threshold \(c\), choose a schedule fixed before signals are known. The schedule is a finite sequence of role blocks whose durations sum to \(\mu_t\) for each \(t\). If \(y_u\) and \(n_u\) are the \(Y\)- and \(N\)-masses in role \(u\), a type-\(t\) block faces margin \(D_t=\sum_{u:A_{tu}=1}(y_u-n_u)/\mu_u\); it chooses \(Y\) when \(D_t\ge c\), \(N\) when \(D_t\le -c\), and otherwise splits according to the signal proportions \(p\) and \(1-p\). What is the complexity of finding a schedule whose final \(Y\)-mass is within additive \(\epsilon\) of the supremum, measured in \(\tau=|T|\), input bit length, \(c\), and \(\log(1/\epsilon)\)?
A non-adaptive cascade on a continuous population divided among finitely many social roles, with rational role masses, role-average interactions, signal probability \(p\), threshold \(c\), and a schedule chosen to maximize final \(Y\)-mass.
Hard instances may require the number of roles \(\tau\) to grow with the graph size, so the case does not show that the mirror compresses the theorem’s hard inputs; this limits the demonstrated scalability rather than the validity of the continuous question.
fatal: False
The mirror covers Theorem 5.3’s non-adaptive, small-\(p\) hardness distinction for maximizing expected \(Y\)-mass. It leaves the adaptive results, the general lower-bound algorithm, and the other non-adaptive results outside its scope.
The strongest mirror I see is the paper’s non-adaptive scheduling problem. Fixing the schedule in advance makes it possible to pass from many similar agents to role masses without also having to preserve the paper’s adaptive response to individual signals.
The anchor is Theorem 5.3, proved in this paper. For the paper’s fixed threshold \(c\), it says that when \(p\) is inverse-polynomial in \(n\), it is NP-hard to distinguish graphs where the best non-adaptive schedule has expected value at least \(n p^{1+\epsilon}\) from graphs where it has value at most \(n p^{c-\epsilon}\), for the stated gap range. The proof reduces from Independent Set, using Lemma 4.1 for the upper bound and Lemma 5.2 for the lower bound. The theorem concerns the underlying scheduling problem, not an encoding.
Here is a continuous version I would ask about:
Block-Fluid Non-Adaptive Cascade Scheduling. An instance consists of a finite set \(T\) of social roles, rational positive masses \(\mu_t\) summing to \(1\), a symmetric zero-one interaction matrix \(A\) with no self-interactions, a rational signal probability \(p\), and the paper’s threshold \(c\). A type \(t\) is a complete description of an agent’s role: agents of that type have the same signal distribution and the same interaction pattern with every role. Mass \(\mu_t\) is the fraction of the population in role \(t\).
Interpret \(A_{tu}=1\) as meaning that a type-\(t\) agent has one contact from role \(u\). Since that role contains a mass of indistinguishable agents, its contribution is represented by its current average choice. If \(y_u\) and \(n_u\) are the masses of role \(u\) that have chosen \(Y\) and \(N\), respectively, the margin faced by type \(t\) is
\[ D_t=\sum_{u:A_{tu}=1}\frac{y_u-n_u}{\mu_u}. \]
A schedule is fixed before signals are known. It is a finite sequence of role blocks, with nonnegative durations summing to \(\mu_t\) for each role \(t\). When a block of type \(t\) is activated, its mass chooses \(Y\) if \(D_t\ge c\), chooses \(N\) if \(D_t\le -c\), and otherwise splits into \(Y\)- and \(N\)-signal mass in proportions \(p\) and \(1-p\). The question is to maximize the final \(Y\)-mass. A solution is a schedule; computationally, one can ask for a schedule within additive \(\epsilon\) of the supremum, with complexity measured in \(\tau=|T|\), the input bit length, \(c\), and \(\log(1/\epsilon)\).
This is a plausible regime when a large population consists of many members of a modest number of recurring roles—say, users in market segments with shared influence patterns. Then \(N\), the population size, is much larger than \(\tau\), and each role contains many agents. The continuous object is the society’s distribution across roles. The role-average interaction is a co-modification of the model: it replaces a named neighbor’s decision with the average decision in that neighbor’s role. The threshold cascade remains order-sensitive and still asks how to schedule decisions to maximize \(Y\).
I would initially investigate hardness transfer. The reduction behind Theorem 5.3 places its combinatorics in an interaction graph through Independent Set. An arbitrary finite role-interaction matrix can still encode graph structure, and fractional masses do not obviously remove the scheduling choices. A useful next question is whether the theorem’s gap survives when each graph vertex is represented by a high-multiplicity role. If it does not, there may be a continuous optimization route, perhaps with algorithms parameterized by \(\tau\). A second question is whether finite role populations converge to this fluid objective, including when \(p\) is small.
The weak point is substantial: Theorem 5.3 is proved for a fixed graph with individually randomized signals. In the fluid model, infinitesimal cohorts split deterministically in proportions \(p\) and \(1-p\), and interactions use role averages. Rare early signal events and individual neighborhoods can drive a cascade in the discrete model; the fluid model may erase them. Thus the theorem does not establish hardness for this mirror. The positive case is that the proposed problem preserves the paper’s central decision rule, scheduling objective, and non-adaptive setting while giving them a natural population-of-roles interpretation. It is a computational optimization question over a continuous society, not merely a mean-field equilibrium question. It covers Theorem 5.3’s non-adaptive inapproximability result; it does not claim to mirror the adaptive results or the paper’s full arbitrary-graph model.
Theorem 5.3 is a real computational result, so the “nothing here to mirror” objection is unavailable. The strongest case against the proposed mirror is that the theorem’s hard input is the specific graph, not a heterogeneous population: every vertex has the same signal probability \(p\) and threshold \(c\), while its exact neighborhood determines whose earlier decisions affect it. In hard instances, grouping vertices by role may leave \(\tau=n\).
The Block-Fluid model groups them by an interaction matrix and replaces individual neighbors’ decisions with role averages. That is a substantial change to the cascade. With one contact per role, thresholding an average is generally different from thresholding each agent’s actual neighborhood; with dense block interactions, keeping a nontrivial threshold may require rescaling \(c\). The Independent Set reduction in Theorem 5.3 relies on exact edges and individual signal histories, so it does not establish hardness for this model. A block-population cascade could still be a worthwhile question, but the theorem is not evidence that it inherits the stated gap.
The stronger way to preserve the graph is to study a large population of repeated copies of the same finite network. That gives a clean continuous distribution over copies’ local cascade states. But the computation then remains inside the finite network motif: the hard graph has not been compressed into a small set of interchangeable individual types. This is the best skeptical point, though it does not settle worth. Such a model could still yield a useful continuous-to-discrete identity or a hardness-transfer result, and the programme explicitly treats those as worthwhile.
So the negative case is weak at its hardest point. It can show that the proposed role-average model is not justified by Theorem 5.3, and that an exact graph-preserving lift retains the theorem’s graph-level complexity. It cannot honestly rule out every plausible repeated-community or block-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.