35 citations · 114 across the 25 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2018★ 19 cited
The Computational Complexity of Training ReLU(s)
Pasin Manurangsi, Daniel Reichman
We consider the computational complexity of training depth-2 neural networks composed of rectified linear units (ReLUs). We show that, even for the case of a single ReLU, finding a…
cs.CC2017
String Matching: Communication, Circuits, and Learning
Alexander Golovnev, Mika Göös, Daniel Reichman +1
String matching is the problem of deciding whether a given -bit string contains a given -bit pattern. We study the complexity of this problem in three settings. Communication…
cs.CC2015★ 1 cited
On Percolation and -Hardness
Daniel Reichman, Igor Shinkar
We consider the robustness of computational hardness of problems whose input is obtained by applying independent random deletions to worst-case instances. For some classical -h…