3 papers
cs.CC2026
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,…
cs.LG2025
On the Depth of Monotone ReLU Neural Networks and ICNNs
Egor Bakaev, Florestan Brunck, Christoph Hertrich +2
We study two models of ReLU neural networks: monotone networks (ReLU) and input convex neural networks (ICNN). Our focus is on expressivity, mostly in terms of depth, and we pr…
cs.LG2024
Depth Separations in Neural Networks: Separating the Dimension from the Accuracy
Itay Safran, Daniel Reichman, Paul Valiant
We prove an exponential size separation between depth 2 and depth 3 neural networks (with real inputs), when approximating a -Lipschitz target function to constant…