In this paper, we explore some basic questions on the complexity of training Neural networks with ReLU activation function. We show that it is NP-hard to train a two-hidden layer feedforward ReLU neural network. If dimension d of the data is fixed then we show that there exists a polynomial time algorithm for the same training problem. We also show that if sufficient over-parameterization is provided in the first hidden layer of ReLU neural network then there is a polynomial time algorithm which finds weights such that output of the over-parameterized ReLU neural network matches with the output of the given data.
The main result of this work is to prove that a two-layer neural network with 2 hidden neurons in the first layer and 1 hidden neuron in the second layer is NP-hard to train when all activation functions are ReLU. Similar results with the hard-thresholding activation function were proved by Blum & Rivest in 1988. The main proof consists of a reduction from the 2-hyperplane separability problem which was known to be equivalent to NNs with hard-thresholding activation functions.
Quality: Moderate. Good solid formal results but nothing really surprising. 
Clarity: The manuscript is mostly well-written, and the authors gave proper credit to prior works. The only minor issue is perhaps the abuse of the variable w in introduction and the same variable w (with an entirely different meaning) in the rest of the paper. It would make more sense to change the w's in introduction to d's.
Originality: This work is largely inspired by Blum & Rivest's work, and builds heavily on some previous work including Megiddo and Edelsbrunner et al. While there is certainly some novelty in extending prior work to the ReLU activation function, it is perhaps fair to say the originality is moderate.
Significance: While the technical construction seems plausible and correct, the real impact of the obtained results is perhaps rather limited. This is one of those papers that it is certainly nice to have all details worked out but none of the obtained results is really surprising or unexpected. While I do agree there is value in formally documenting the authors' results, this conference is perhaps not the right venue. 
Other comments: The discussion on page 2 (related literature) seems odd. Wouldn't the results of Livni et al and Dasgupta et al already imply the NP-hardness of fully connected ReLU networks, in a way similar to how one obtains Corollary 3.2? If this is correct, then the contribution of this work is basically a refined complexity analysis where the ReLU network is shrunken to 2 layers with 3 nuerons?
I really wish the authors had tried to make their result more general, which in my opinion would make this paper more interesting and novel: can you extend the proof to a family of activation functions? It is certainly daunting to write separate papers to prove such a complexity result for every activation function... The authors also conveniently made the realizability assumption. What about the more interesting non-realizable case?
The construction to prove Theorem 3.4 bears some similarity to a related result in Zhang et al. The hard sorting part appears to be different.