I haven't read the paper, but most of the time, in order to achieve matching outputs with less layers, you will need exponentially more neurons per layer.
If you have infinite parallelism I believe the shallow network would be faster, but deep networks will use less total operations and will be faster in practice.