  We show that any depth-$d$ circuit for determining whether an $n$-node graph
has an $s$-to-$t$ path of length at most $k$ must have size
$n^{\Omega(k^{1/d}/d)}$. The previous best circuit size lower bounds for this
problem were $n^{k^{\exp(-O(d))}}$ (due to Beame, Impagliazzo, and Pitassi
[BIP98]) and $n^{\Omega((\log k)/d)}$ (following from a recent formula size
lower bound of Rossman [Ros14]). Our lower bound is quite close to optimal,
since a simple construction gives depth-$d$ circuits of size $n^{O(k^{2/d})}$
for this problem (and strengthening our bound even to $n^{k^{\Omega(1/d)}}$
would require proving that undirected connectivity is not in $\mathsf{NC^1}.$)
  Our proof is by reduction to a new lower bound on the size of small-depth
circuits computing a skewed variant of the "Sipser functions" that have played
an important role in classical circuit lower bounds [Sip83, Yao85, H{\aa}s86].
A key ingredient in our proof of the required lower bound for these Sipser-like
functions is the use of \emph{random projections}, an extension of random
restrictions which were recently employed in [RST15]. Random projections allow
us to obtain sharper quantitative bounds while employing simpler arguments,
both conceptually and technically, than in the previous works [Ajt89, BPU92,
BIP98, Ros14].
