  In this work, we analyze dimension reduction algorithms based on the Kac walk
and discrete variants.
  (1) For $n$ points in $\mathbb{R}^{d}$, we design an optimal
Johnson-Lindenstrauss (JL) transform based on the Kac walk which can be applied
to any vector in time $O(d\log{d})$ for essentially the same restriction on $n$
as in the best-known transforms due to Ailon and Liberty [SODA, 2008], and
Bamberger and Krahmer [arXiv, 2017]. Our algorithm is memory-optimal, and
outperforms existing algorithms in regimes when $n$ is sufficiently large and
the distortion parameter is sufficiently small. In particular, this confirms a
conjecture of Ailon and Chazelle [STOC, 2006] in a stronger form.
  (2) The same construction gives a simple transform with optimal Restricted
Isometry Property (RIP) which can be applied in time $O(d\log{d})$ for
essentially the same range of sparsity as in the best-known such transform due
to Ailon and Rauhut [Discrete Comput. Geom., 2014].
  (3) We show that by fixing the angle in the Kac walk to be $\pi/4$
throughout, one obtains optimal JL and RIP transforms with almost the same
running time, thereby confirming -- up to a $\log\log{d}$ factor -- a
conjecture of Avron, Maymounkov, and Toledo [SIAM J. Sci. Comput., 2010]. Our
moment-based analysis of this modification of the Kac walk may also be of
independent interest.
