Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent

Parity functions are fundamental Boolean operations with critical applications across machine learning, cryptography, and error correction. Yet, learning high-dimensional parity functions poses significant challenges: in a general setting, standard neural network architectures typically require exponential sample complexity, making gradient-based optimization intractable for large number of inputs $N$. We demonstrate that compact product-based neural architectures combined with stochastic data sparsity (Bernoulli inputs with $p_e \leq 1/N$) and appropriate hyperparameter choice enable efficient parity learning, with theoretical guarantees of convergence. Experiments validate our theory across dimensions up to $N = 100{,}000$, with empirical evidence showing optimal hyperparameter choices for $p_e$ and learning rate $\alpha$, as well as polynomial complexity scaling laws. This work establishes fundamental connections between architectural inductive bias and data sparsity, opening new possibilities for neural arithmetic, structured reasoning, binary neural networks, and machine learning applied to automated protocol discovery.

Imagine thousands of switches, only some of which are connected to a light: the light turns on whenever an odd number of those connected switches are flipped. Now imagine two identical panels following this same rule — one with fixed secret wiring you cannot see, the other yours to rewire freely. You set the same switch configurations on both panels simultaneously, observe whether their lights agree, and gradually adjust your wiring until both panels respond identically to any configuration. This is the parity learning problem — and identifying the secret wiring turns out to be notoriously hard for AI under standard training methods, which require an astronomically large number of trials. We show that two ingredients together unlock efficient learning. First, we leverage a product-based neuron — one that multiplies its inputs rather than summing them — whose structure naturally aligns with parity logic. Second, we train it on sparse configurations, where each switch is most likely to be off, which transforms an otherwise chaotic search into a well-behaved one. Together, these choices allow standard AI training, from very few observations, to reliably identify the secret switches in problems involving up to $100{,}000$ switches, with mathematical proof of when and why it works. Beyond parity itself, our results suggest a broader design principle: aligning a network's structure with its target problem, combined with structured data, can turn previously intractable learning problems into tractable ones — with direct applications to error-correcting codes, cryptography, and AI systems that need to perform logical reasoning.