Lower bounds over Boolean inputs for deep neural networks with ReLU gates

Anirbit Mukherjee, Amitabh Basu

Motivated by the resurgence of neural networks in being able to solve complex learning tasks we undertake a study of high depth networks using ReLU gates which implement the functi…