Starflower V: Robustness, Neural Interpretation, and the NC Frontier
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
This fifth Starflower paper elevates the framework from a single inheritance theorem to a structured research program with three pillars: robustness, neural interpretation, and an explicit NC frontier. It systematizes the robustness of the Starflower Inheritance Theorem against several natural “attack vectors” on bounded-negation hardness, including negation bottlenecks, semantic hashing and selector gadgets, mixtures of implicant lengths, and the introduction of XOR and adaptive models (carefully scoped as out-of-model). Within the DeMorgan framework and the Jukna–Lingas negation-width measure, the paper shows that these strategies are either already priced into the existing penalty factor or lie cleanly outside the scope of the theorem. On the neural side, it develops a McCulloch–Pitts interpretation in which inhibitory width corresponds to circuit negation width, yielding exponential lower bounds on the number of neurons required for networks with bounded inhibition to compute monotone-hard functions such as bipartite perfect matching. Finally, the paper identifies a concrete next frontier: depth-sensitive (NC-style) analogues of the Jukna–Lingas theorem and a corresponding Starflower-for-NC inheritance result, together with a plan for small neural prototypes that exhibit the same inhibitory-width blow-up on toy instances.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 28 March 2026
- Language
- EN
- Document type
- Preprint