Starflower V: Robustness, Neural Interpretation, and the NC Frontier

Read full text Summarise with VIRAT
Authors: Richard Brazil
Cited by: 0

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