Depth Lower Bounds for ReLU Networks with Binary Inputs

Neil Krishnan, Elchanan Mossel

We study the role of depth in ReLU networks with discrete (Boolean) inputs and real-valued outputs, complementing two established lines of work. For Boolean inputs, striking depth…