CS Paper Radar

Neural Logic, Invariance, and the Retina---McCulloch and Pitts

Nima Dehghani

cs.FL q-bio.NCcond-mat.dis-nncs.NEphysics.bio-ph ·submitted 2026-09-02 06:47 UTC · v1

Abstract

This chapter reconstructs the McCulloch-Pitts program as a physics of neural computation rather than the familiar cartoon of a binary neuron. The 1943 logical calculus is developed in both directions: given a net, characterize the propositions realized by its activity; given an admissible logical expression, construct a net that realizes it. We recover the original distinction between thresholded excitatory summation and absolute inhibitory veto-one the weighted-threshold form cannot preserve for arbitrarily large excitatory inputs-and read unit-time delay as the physical realization of logical depth. Recurrence is treated exactly: an autonomous, deterministic network of finitely many binary units has a finite state space, so every trajectory eventually enters a periodic orbit-a fact about finite-state dynamics, not unbounded Turing computation. A single threshold element realizes only linearly separable Boolean functions, whereas finite feedforward networks of them synthesize any Boolean function on a finite domain. We then follows McCulloch and Pitts beyond threshold logic. The 1945 heterarchy paper turns cyclic preference into an obstruction to representation by a scalar utility. The 1947 work on universals asks how a physical network can identify inputs related by nuisance transformations, developed here via group averaging and feedback canonicalization. The 1959 frog-retina study makes the adequate-stimulus question experimental, revealing parallel invariant operations before the brain proper. Spike-triggered analysis shows how a nonlinearly driven neuron can have a vanishing first-order average while second-order statistics recover its hidden selectivity: methodological failure can masquerade as physiological absence. Modern mathematical tools are used without projecting their notation onto the historical papers, and limitations of the idealization are stated explicitly.

Comment
Book chapter from NeuroAI: Theoretical Foundations of Dynamics, Learning and Computation in Brains, Minds, and Machines. Includes reproducible figures and accompanying code

Closest papers

Nearest neighbours by meaning across the whole index.

On the Number of Observation Nodes in Recurrent Neural Networks with Linear Threshold and ReLU Functions

eess.SY ·2026-08-30 ·Liangjie Sun, Wai-Ki Ching, Tatsuya Akutsu
theory similarity 0.57
Abstract

This paper investigates how node update rules and admissible state domains affect the minimum number of observation nodes required for global finite-horizon observability in recurrent neural networks with linear-threshold and ReLU update functions. Over a common binary state domain, we construct a class of $K$-linear-threshold ($K$-LT) networks whose initial states can be uniquely reconstructed from the finite output trajectory of a single observation node. We further establish a dynamical equivalence between binary-valued $K$-ReLU networks and $K$-AND Boolean networks, which transfers existing class-level observation-node bounds to binary-valued $K$-ReLU networks. For nonnegative-valued ReLU networks, the observability problem reduces to the classical linear-system setting whenever the relevant pre-activations remain nonnegative. For general real-valued ReLU networks, we prove that global finite-horizon observability requires at least $n/2$ observation nodes when no restriction is imposed on the number of state variables involved in each node update. This lower bound is tight when $n=2K$, for which we construct a $K$-ReLU network observable from exactly $K$ nodes. These results show that both update rules and state domains fundamentally affect extremal observation requirements: temporal evolution can concentrate finite-state information into a single measured trajectory, whereas activation-induced rank loss creates an intrinsic sensor lower bound in continuous-state ReLU networks.

0.29

Recurrent Graph Neural Networks with Set-Based Aggregation

cs.AI ·2026-09-14 ·Blai Bonet
similarity 0.56
Abstract

Recurrent GNNs iterate message passing to convergence, and their logical characterizations to date rely on multi-set aggregation, graded (counting) logics, and halting or acceptance conditions that cannot be verified from the network's parameters. We study recurrent GNNs with set-based aggregation and identify sufficient conditions checkable from the weights for networks to compile into formulas and formulas into networks. The main result is an effective, two-directional equivalence between a class of networks and the Boolean closure of reachability and safety properties, the fragment B$Σ^{\circ}_1$ of the modal $μ$-calculus. The fragment is not an artifact: it is the exact expressive level of stabilization over finite vocabulary, which supports fixed points of a single polarity and Boolean combinations thereof, but not the composition of fixed points of opposite polarities. The correspondence needs no counting logic, no external halting signal, and no non-effective acceptance condition, yielding a verifiable path from weights to symbolic explanations for networks meeting the conditions.

0.27

The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought

cs.LG stat.ML ·2026-10-12 ·Roey Magen, Nirmit Joshi, Gal Vardi
hot direction similarity 0.56
Abstract

The success of autoregressive language models trained with Chain-of-Thought~(CoT) supervision raises a fundamental question: How simple can a next-token predictor be while still enabling the efficient simulation of general computation through its autoregressively generated CoT? Surprisingly, we show that a single neuron suffices. For a broad family of activations, including threshold and ReLU, a single autoregressive neuron can simulate any feedforward circuit with the same activation. Specifically, a size-$s$ circuit on $n$ inputs can be simulated by a neuron of dimension $O(ns+s^2)$ using $O(s^2)$ generation steps, with both bounds independent of circuit depth and tight under natural assumptions. For threshold activations, this improves upon the simulation of Joshi et al. (COLT 2025), whose bounds scale exponentially with circuit depth. Consequently, autoregressive threshold neurons can simulate polynomial-time Turing machines, while remaining efficiently learnable from CoT supervision. Our main expressivity result relies on a novel connection to Sidon sets from additive combinatorics. As an experimental illustration, we efficiently train a single autoregressive ReLU neuron to mimic a neural network teacher with nontrivial test accuracy on CIFAR-10.

0.53

Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization

cs.LG cs.AIstat.ML ·2026-09-11 ·Hrad Ghoukasian, Anastasis Kratsios
theory similarity 0.56
Abstract · 58 pages, 7 figures, 6 tables

As compute scales, models evolve, and training algorithms advance, our ability to explain the increasingly powerful AI systems they enable is eroding. To help safeguard interpretability, we introduce a specialized training algorithm (MACCHIATO) that jointly constructs (i) an explicitly structured $\operatorname{ReLU}$-MLP from partial truth-table observations and (ii) an explicit Boolean circuit over signed literals with $\{\operatorname{AND},\operatorname{OR},\operatorname{XOR}\}$ gates certifying what its subnetworks compute and how they compose. Intuitively, we iteratively project the residuals of a Boolean function onto low-dimensional $\{\operatorname{AND},\operatorname{OR},\operatorname{XOR}\}$-circuit classes and exactly compile the resulting circuit into a $\operatorname{ReLU}$-MLP; we combine $\operatorname{ReLU}$-MLP circuit compilation, ESPRESSO logic minimization, and influence-based variable selection. Roughly speaking, our interpretability certificate is complemented by a statistical guarantee: under the theorem's influence-recovery conditions, if each of the $m$ stage-wise residuals depends on at most $\log_2(B)$ bits, a sample-splitting variant of our algorithm trained on $T$ observations returns a six-layer $\operatorname{ReLU}$-MLP (counting the input layer) of width $\mathcal{O}(mB)$ with truth-table error $\mathcal{O}\bigl(\sqrt{m(B+\log(m/δ))/T}\bigr)$. On synthetic random-junta tasks, our networks outperform depth- and hidden-width-matched Adam-trained MLPs in several data-sparse or projection-aligned regimes, while the trained ReLU-MLPs are stronger in others. Moreover, in our explicit PyEDA truth-table implementation, the iterative procedure completes in regimes where flat ambient-dimensional ESPRESSO exceeds the three-hour computational budget.

0.49

Non-Zero Radius: The Missing Component of Neural Networks

cs.AI ·2026-10-29 ·Tiansi Dong, Mateja Jamnik, Pietro Liò
publishedposition similarity 0.55
Abstract · 5 pages, 7 figures

Inspired by the analogy between the all-or-none activation of biological neurons and the true-false of logic circuits, McCulloch and Pitts proposed a mathematical model of the biological neuron in 1943 with the aim of simulating logical reasoning. Although Norbert Wiener considered the model overly simplistic at the time, it later became a building block of modern neural networks, including large language models. Despite their remarkable empirical success, however, conventional neural networks remain largely black-box systems and struggle with reliable symbolic reasoning. Viewing vectors as spheres of zero radius, we relax the zero-radius constraint and represent concepts as spheres with non-zero radii. We argue that sphere-based representations can capture additional features of biological cognition, including representing spatial concepts as regions and reasoning through model construction and inspection. Building on sphere embeddings, we introduce Sphere Neural Networks (SphNNs), which use a transition map to achieve symbolic-level Aristotelian syllogistic reasoning without training data, thereby taking an initial step toward the original goal of McCulloch and Pitts. We suggest that the zero-radius constraint may reflect an aspect of the oversimplification identified by Wiener and may limit conventional neural networks' capacity for symbolic-level logical reasoning.

0.42

Security Properties of Neural Networks as Decision Problems

cs.LO cs.CCcs.CRcs.LG ·2026-09-30 ·Adrian Wurm
theory similarity 0.54
Abstract · 26 pages, 1 table

Certifying a deployed neural network raises decision problems that the verification literature has not classified: whether the model carries a backdoor planted in its training data, whether a fault in its stored parameters can drive it into an unsafe state, whether its output leaks a private part of its input. We formalise eight such problems and classify what we can. The organising observation is a logical one. The function computed by a piecewise linear network, together with all its node values, is definable by a quantifier-free formula of real addition of size linear in the network, so a property of the network is a quantifier-alternation sentence, which Sontag's 1985 theorem places in the polynomial hierarchy at the level of its prefix. Membership results are thus corollaries, and the argument makes plain what they need: that the quantified objects are inputs rather than the network's own parameters. Non-interference, monotonicity and counterfactual fairness have exactly the complexity of network equivalence and of interval verification, all co-NP- complete over ReLU. Detection of backdoor triggers from a quantised alphabet is Sigma_2^P-complete, one level above robustness certification, so it does not reduce to polynomially many robustness queries unless the hierarchy collapses. Inversion resistance is co-NP-complete for every l_p metric, p a fixed positive integer. Quantifying over parameters instead of inputs - the fault model of bit-flip attacks, radiation upsets and analog accelerators - makes verification exists-R-complete already for networks of identity nodes, for which every previously studied problem is in P, and it stays so when each parameter is confined to a box of inverse-polynomial width; the corresponding safety question is forall-R-complete for ReLU.

0.28

New Gate, Weight and Wire Complexity Bounds for Sigmoid Neural Networks

cs.CC ·2026-11-16 ·Jiatu Li, Daniel Reichman, Ryan Williams, Tony Wu
theory similarity 0.54
Abstract

Feedforward neural networks with sigmoid activations are of fundamental importance in neural computation. However, our understanding of the circuit complexity of such networks for implementing Boolean functions remains limited. The analog output of the sigmoid, along with its transcendental nature, leads to unique mathematical challenges for proving lower bounds. Introducing new techniques, we establish new upper and lower bounds on the complexity of sigmoidal networks computing Boolean functions: We prove nearly tight bounds for the wire complexity of computing PARITY with such networks of constant depth and polynomial-bounded weights. We extend the size lower bound of Kane and Williams [STOC'16] against depth-$3$ threshold circuits, to depth-3 sigmoidal networks with polynomial weights, proving a $Ω(n^{1.5}/(\log n)^{O(1)})$ size lower bound for computing an explicit function in $\mathsf{P}$. We prove that every symmetric function on $n$ bits can be computed by a depth-$3$ sigmoidal network with $O(n)$ wires and polynomial weights. This stands in stark contrast with threshold circuits of $d=O(1)$ depth, where $n^{1+α_d}$-wire lower bounds are known for $α_d > 0$. We also answer a few fundamental problems related to sigmoidal networks, including proving new simulations and separations between threshold circuits and sigmoidal networks. We establish these results using a variety of techniques, including random restrictions for sigmoid gates, analyzing the average sensitivity of networks with sigmoids, simulation arguments, and using tools from approximation theory, complex analysis, and algebraic geometry.

0.44

The Ball and the Box: Two Geometries of Computation in Superposition

cs.LG ·2026-10-08 ·Xiaoyu Li, Lequan Lin, Dai Shi, Jiaojiao Jiang, Junbin Gao +1 more
similarity 0.53
Abstract

Neural representations can encode more features than they have dimensions, a phenomenon known as superposition. We study the dimension needed to compute Boolean gates from such representations. For a single threshold layer with a Gaussian random dictionary and uniformly random sparse Boolean inputs, we derive sharp dimension thresholds under two error criteria. A vanishing expected error count can require more dimensions than correctness of every output with high probability. Shared reads explain the gap: rare realizations can produce many errors at once. The expected-count threshold has ball geometry, while joint reliability has box geometry when a gate is evaluated on every feature tuple. Optimizing shared readout weights and biases gives explicit thresholds for conjunction, disjunction, and majority. For pairwise conjunction, the analysis also describes the transition near the threshold, in agreement with exact simulations.

0.25