The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

Moritz Stargalla, Christoph Hertrich, Daniel Reichman

An established measure of the expressive power of a given ReLU neural network is the number of linear regions into which it partitions the input space. There exist many different,…