| paper | d4-conf-ecai-2023-0025 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: For every fixed \(0<\epsilon<1\), a polynomial-time \(\mathcal O(2^{(\log_2\tau)^{1-\epsilon}})\)-approximation is impossible unless \(\mathrm{NP}\subseteq\mathrm{DTIME}(n^{\operatorname{polylog}n})\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\), a symmetric nonnegative contact matrix \(A=(a_{tu})\), thresholds \(\theta_t\), and a budget \(B\), can one decide whether there is a finite timed schedule of targeted masses with total cost at most \(B\) that makes every type fully positive on a final unforced update? At time \(i\), let \(p_t(i)\) be the positive mass of type \(t\), and set \(e_t(p(i))=\frac{\sum_u a_{tu}p_u(i)}{\sum_u a_{tu}\mu_u}\). Initially \(p_t(0)=s_t(0)\); thereafter, \(p_t(i)=\mu_t\) if \(e_t(p(i-1))\ge\theta_t\), and \(p_t(i)=s_t(i)\) otherwise, with \(0\le s_t(i)\le\mu_t\). The schedule must have \(s_t(k)=0\) and \(p_t(k)=\mu_t\) for every type at its final step \(k\); its cost is \(\sum_{i=0}^k\sum_t s_t(i)\).
Types are cohorts with identical thresholds and contact profiles, carrying rational masses \(\mu_t\). The symmetric matrix \(A\) specifies block-level contacts; decisions \(s_t(i)\) are real targeted masses, and the objective is their total over a finite schedule ending in an unforced all-positive update.
Theorem 6's reduction uses local sparse gadgets, so it does not establish hardness for the block-mixed model; the proponent acknowledges that a separate argument is needed.
fatal: False
The mirror covers Theorem 6's minimum-TTS hardness question. It leaves aside the structural bounds, the tree algorithm, the greedy algorithm, and the experiments.
The strongest mirror I see is Type-Mass Timed Target Set Selection. Imagine a large online community whose members can change between two stances under non-progressive threshold updates. A type specifies an agent’s threshold and full contact profile: everyone of type \(t\) has the same normalized pattern of contact with every other type. Let \(\mu_t\) be type \(t\)’s fraction of the population, with \(\sum_t\mu_t=1\). The interaction structure is a symmetric nonnegative matrix \(A\); an agent of type \(t\) receives contact weight \(a_{tu}\) from each member of type \(u\). If \(p_u(i)\) is the positive mass of type \(u\) at time \(i\), type \(t\)’s positive-neighbor share is \(e_t(p(i))=\frac{\sum_u a_{tu}p_u(i)}{\sum_u a_{tu}\mu_u}\). Its threshold is a fraction \(\theta_t\). The agents’ stances remain binary; only their aggregate mass can be fractional.
At each discrete time, the campaign may force a mass \(s_t(i)\) of type \(t\) positive, paying for that mass again if it targets it at another time. If \(e_t(p(i-1))\ge\theta_t\), the whole type becomes positive naturally; otherwise its positive mass at time \(i\) is the mass targeted then. Initially \(p_t(0)=s_t(0)\). The goal is to find a finite schedule ending with every type fully positive on an unforced update, minimizing \(\sum_i\sum_t s_t(i)\). A decision version asks whether such a schedule of cost at most \(B\) exists. The instance is the rational type masses, contact matrix, thresholds, and budget; a solution is the finite sequence of targeted masses. This preserves the paper’s repeated, timed intervention and total targeting cost, while making the population—not time or opinion—continuous.
A plausible regime is a platform with millions of users in large, structurally similar cohorts: users in a cohort have the same stance threshold and the same mix of contacts across cohorts. The number of agents \(N\) can greatly exceed the number of types \(\tau\). A dense block network gives this model a direct interpretation: members of a cohort have the same contact pools, and thresholds become fractions of their neighborhood. A base graph can describe which cohorts interact. The type definition includes the whole contact profile, so aggregation does not erase idiosyncratic costs or preferences; it groups agents only when the model treats them identically.
My lead anchor is Theorem 6, proved in this paper using a reduction from the progressive target-set problem. It states that Timed Target Set Selection cannot be approximated within a ratio of \(\mathcal{O}(2^{\log^{1-\epsilon}n})\), for any fixed \(\epsilon>0\), unless \(NP\subseteq DTIME(n^{polylog(n)})\). The reduction constructs a non-progressive instance with attached \(K_2\) gadgets and establishes equality between its optimum and the progressive instance’s optimum; the underlying progressive inapproximability is cited from earlier work. This is a hardness result for general graphs and threshold assignments, not just for the paper’s experiments or special graph families.
The continuous question is whether Type-Mass Timed Target Set Selection admits an efficient algorithm, or whether a comparable inapproximability result holds, with complexity measured in \(\tau\) and the rational input bit length. The interaction matrix retains the network topology that drives threshold cascades, so I would provisionally expect Class B: hardness transfers. The hard combinatorics appear to live in the graph of interacting roles, not merely in the number of individual agents; cloning each role can make the population arbitrarily large without removing that topology. But Theorem 6 does not prove this prediction. Its reduction preserves the discrete optimum, whereas fractional targeting inside a type may create cheaper schedules. A transfer proof would need to control that fractional advantage, ideally with a gap-preserving reduction or a rounding theorem.
This mirror covers the paper’s general minimum-TTS hardness result, not every result in the paper. It asks whether the same timed manipulation problem becomes easier when large groups of agents share a complete interaction profile. That is a computational question about intervention in a continuous population, distinct from analytic mean-field questions about whether the dynamics converge.
The weakest point is the structural assumption: exact shared contact profiles are a strong idealization, and in sparse or highly individual networks the number of types may be nearly the number of agents. More seriously for the hardness claim, fractional targeting may defeat the paper’s reduction even when the blow-up scenario is sensible. I would still put this question to the authors because the type-mass model keeps their threshold process, timing, and intervention objective intact, and asks precisely whether high multiplicity changes its complexity. Further questions include whether the optimum can be rounded to a finite cohort instance with controlled loss, whether bounded-treewidth interaction graphs admit algorithms analogous to the paper’s tree result, and how the continuous optimum compares with discrete TTS on large replicated networks.
Theorem 6 is the right anchor to attack, because it is the paper’s clearest computational result: TTS inherits a strong inapproximability bound through a reduction from progressive target set selection. The difficulty is that its input is an arbitrary graph whose vertices have individual, integer-valued neighborhoods. To preserve that model exactly, a “type” must include the vertex’s full contact profile and threshold. In most graphs, that leaves nearly one type per vertex, so there is no high-multiplicity regime to continuize.
The proposed type-mass model avoids that problem by replacing individual neighborhoods with aggregate contact weights. That is coherent for a large, densely mixed community with role-based contacts. But it describes weighted block networks, not the arbitrary sparse graphs in Theorem 6. In the paper’s model, which particular neighbors are positive determines whether a node crosses its threshold. Type masses alone generally lose that information. The theorem’s reduction makes the distinction concrete: it attaches local \(K_2\) gadgets to encode progressive behavior. A type-level average does not preserve those local dynamics or the reduction’s equality of optima. This does not show that the continuous problem is uninteresting; it shows that Theorem 6 does not establish its hardness.
The strongest repair is to study block-structured networks directly, with cohorts of agents sharing the same normalized contact pattern and fractional targeting. That is a legitimate computational question and could be a sensible mirror if the authors accept the weighted, dense-network model. But preserving sparse, finite-degree contacts while aggregating agents would require more than a finite list of cohort masses: one would need to retain distributions of local neighborhoods or contact histories. That moves away from the paper’s finite graph input and from the proposed model’s small type space.
So the negative case is that the available mirror choices pull apart: preserve the paper’s network dynamics and usually lose multiplicity, or obtain a compact population model by changing the network to a block-mixed one. I would argue against making this a priority mirror on that basis. But I cannot honestly say the anchor is defeated: the block-network version is plausible, well-posed, and computational. Under the programme’s stated gate, a reader could reasonably conclude that it survives.
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.