Computational Math with Neural Networks is Hard

Abstract

We establish asymptotic complexity barriers for three basic numerical tasks with neural-network data: integration of a network realization, solution of a Poisson problem with a neural-network right-hand side, and multiplication by a neural-network encoded matrix. A common reduction encodes Boolean formulas as ReLU networks and reduces Boolean satisfiability to each task. Any algorithm improving on the resulting convergence-rate bounds would contradict the Strong Exponential Time Hypothesis (SETH). These bounds hold even with full access to the network representation, including all weights. The core reductions use networks with three hidden layers, width linear in the number of Boolean variables, bounded realizations, and sparse connectivity. A finite-precision Monte Carlo quadrature attains the optimal rate for integration up to logarithmic factors, so the lower bound for integration is sharp. We show slightly weaker lower bounds for networks with two hidden layers and provide fast quadrature algorithms for one-hidden-layer networks.