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

ArXi:2605.28612v1 Announce Type: new 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