Evidence of exponential speed-up in the solution of hard optimization problems?

Immediate skeptical question: what arity (fan-in) do the authors consider reasonable for the multi-terminal AND/OR gates?

If you assume that you can have arbitrarily large arity gates without incurring additional delays (which is NOT generally realistic), you get a very different result than if you assume there can be at most, say, 10 inputs to a gate without introducing additional delays.