| paper | d4-conf-aaai-2021-0130 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Theorem 4.4 is a named PSPACE-completeness result, so it has computational character. But in the paper, each vertex reads fixed predecessor states; cloning vertices does not make state marginals determine next-step masses when those states are correlated. Independent resampling closes the proposed dynamics, but makes it a different reachability problem that the Boolean-corner embedding does not turn into a continuous version the authors would recognize.
fails bit b-changes — the continuum limit changes the question
Fixed predecessor identities create correlations that type-level state fractions do not capture; independent resampling removes those correlations by changing the paper’s fixed-network dynamics.
fatal: True
The candidate targets only Theorem 4.4; it leaves the phase-space bounds, the convergence-guarantee result, and the monotone-DAG algorithm without mirrors.
The strongest mirror I believe is Mean-Field DAG Reachability. Its agents are members of a large population divided into roles. A type is a role together with its local Boolean update rule and its list of upstream input roles; agents of that type are otherwise indistinguishable. The society is a distribution \(\mu\) over these types. For each type \(t\), let \(p_t\in[0,1]\) be the fraction of its mass currently in state \(1\). The role graph is a DAG, and every member of a type uses the same synchronous update rule.
To close the dynamics at the level of type masses, suppose each upstream input slot is filled by an independently sampled member of its specified source type. If \(f_t\) is the original symmetric Boolean rule for type \(t\), define its mean-field update by
\[ F_t(\mathbf p) = \mathbb E\!\left[ f_t(X_{\mathrm{self}},X_{u_1},\ldots,X_{u_d}) \right], \]
where the bits are independent, \(X_{\mathrm{self}}\sim\mathrm{Bernoulli}(p_t)\), and \(X_{u_i}\sim\mathrm{Bernoulli}(p_{u_i})\) for each upstream input slot. Thus \(\mathbf p^{k+1}=F(\mathbf p^k)\) is a deterministic update of the population fractions. For an instance, give the DAG of types, positive rational masses \(\mu_t\) summing to \(1\), each type’s symmetric Boolean rule, and rational initial and target vectors \(\mathbf p^0,\mathbf q\in[0,1]^\tau\). Ask whether there is a finite \(k\ge 0\) with \(F^k(\mathbf p^0)=\mathbf q\); a solution is such a time \(k\). The mass of type \(t\) in state \(1\) is \(\mu_t p_t\).
My anchor is Theorem 4.4, proved in this paper: Reachability for DAG-SyDSs with symmetric local functions is PSPACE-complete. The theorem follows from the paper’s own Theorems 4.1 and 4.3: the first establishes PSPACE-completeness for \(r\)-symmetric local functions with \(r\le 6\), and the second reduces those instances to ones with symmetric local functions while preserving the DAG property. This is a hardness anchor, not a claim that the paper’s continuous analogue is already known.
The mirror has an exact discrete embedding. If every \(p_t\) is \(0\) or \(1\), then the sampled input bits are deterministic, so \(F\) reproduces the original local updates exactly. Boolean-corner states remain Boolean, and the paper’s reachability question is precisely the restriction of this mean-field question to those states. The mirror therefore retains the paper’s PSPACE-hard instances. I would provisionally classify it as hardness transfers: the hardness is carried by the role graph and its local logic, not by having a small population. The complexity of reachability from arbitrary fractional states is a further question; I would not infer PSPACE-completeness for the full rational-fraction problem from Theorem 4.4 alone.
A plausible regime is a very large layered organization or information-propagation system with many agents per role, all following the same update rule and drawing inputs from the same upstream role cohorts. The total population can be much larger than the number of roles \(\tau\), while \(\tau\) still grows with the computational instance. This is not a claim that arbitrary fixed networks are automatically mean-field systems. It is a particular high-multiplicity regime in which role-level fractions are the natural state description. Mean-field opinion dynamics supplies familiar machinery here; the mirror’s question is computational reachability, rather than equilibrium existence or structure.
The scope is deliberately narrow: it mirrors the symmetric-DAG Reachability result, not the paper’s phase-space bounds, Convergence Guarantee result, or monotone-case algorithm. The main weakness is the co-modification: the paper gives agents fixed incoming edges and deterministic updates, whereas this mirror uses independent sampling and an expected population update. That could make authors regard it as a nearby model instead of their problem’s continuous form. I think the case survives because the change has a concrete repeated-role interpretation, preserves the authors’ local rule on every coherent discrete configuration, and makes fractional population states meaningful while keeping the computational question finite-time reachability. The next questions would be whether arbitrary fractional orbits add continuum-specific hardness, and what finite-population approximation guarantees connect this mean-field dynamics back to fixed or sampled networks.
Theorem 4.4 is a genuine computational result, and the Boolean-corner argument is exact: on \(p_t\in\{0,1\}\), the proposed update recovers the paper’s reachability instances. I can’t dismiss that by saying hardness transfers; that would be a valid Class B mirror if the model clears the authors’ recognition gate.
My concern is that the proposed model changes what the graph means. In the paper, an incoming edge identifies a particular vertex whose state is read. Symmetric local functions ignore the *order* of those inputs, not their identities. For a faithful high-multiplicity model, two agents therefore need the same relevant wiring as well as the same rule. Replicating a DAG as many identical copies preserves that wiring, but the state of a node is correlated with the states of its particular predecessors. The marginal fractions \(p_t\) do not generally determine the next fractions. Tracking the distribution over whole-copy configurations would preserve the dynamics, but it would make the “types” entire configurations, with up to \(2^n\) possibilities; identical copies simply repeat the original trajectory.
Independent resampling of upstream agents each round closes the equations at the level of \(p_t\), but it replaces the paper’s fixed DAG with an annealed random-interaction network. A fixed random network does not generally fix the problem: dependencies create correlations over time, so the marginal update need not be the proposed expectation. Dense mixing or resampled contacts may be sensible for some opinion-diffusion settings, but they are additional modelling commitments, not consequences of the paper’s reachability result. My negative case is that the anchor is a nearby mean-field problem rather than a continuization of this paper’s fixed-network problem.
That case is not airtight. A large layered organization with many agents per role and resampled contacts is plausible, and finite-time reachability for its mean-field map appears to be a real computational question. If the authors would recognize that as their problem, this anchor survives; the paper’s deterministic fixed-edge formulation is the main reason I doubt they would.
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.