Compositional Incoherence is a Parity
Local Audit Carries Zero Signal; Recovering Conventions from Observation is SQ- and LPN-Hard
When is compositional incoherence invisible to bounded-radius certification?
Recovering the compositional obstruction from r-local observation is SQ-hard (q ≥ (2^k-1)τ²) and LPN/LWE-hard under noise — local interpretability sees zero cyclic signal by a complexity barrier, not a tooling gap
The parity reduction remains at paper level and awaits independent review.
Abstract
Semantic coherence of a composition is agreement of the conventions its components attach to shared quantities around every cycle; a companion impossibility result shows no bounded-radius local audit can certify it. This paper recasts certification as learning, from one observation: the holonomy of a composition around a cycle is a parity of edge signs, so recovering its coherence structure is learning a parity. Three results follow. On a graph of girth > 2r the radius-r local views are identical across all obstructions, so local interpretability obtains zero signal at any sample size. Detection is trivial but recovery is statistical-query-hard: any correlational-SQ learner needs q ≥ (2^k-1)τ² queries, exponential in the cycle-count. Under noisy observation, recovery is LPN/LWE-hard in the abelian regime. The barrier is complexity-theoretic, not a tooling limitation.
A flaw in the reduction or an algorithm violating the stated lower bound.
not requested