Epipolar sampling is one of the main speedups. Basically instead of raymarching naively you raymarch in a regular fashion with samples radiating from the screenspace position of the lightsource out to the edges of the screen. Then take into account edge detection, which can again be done in screenspace, for high contrast variations and you suddenly have a lot less samples to go through.
1d Min/Max take advantage of the above. Epipolar sampling gives you what looks sort of like a 1d heightmap, which is then used to speed things up again.
A gross simplification, but I hope I just wrote something coherent enough. The intel paper ends up with only a little over 2ms on a GTX680, at least with their lowest quality setting.