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.
Threshold Derivation
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.
Geometry of Thresholds
The expected-count threshold has ball geometry, while joint reliability has box geometry when a gate is evaluated on every feature tuple.
Threshold Optimization
Optimizing shared readout weights and biases gives explicit thresholds for conjunction, disjunction, and majority.
Pairwise Conjunction
For pairwise conjunction, the analysis also describes the transition near the threshold, in agreement with exact simulations.