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Ω(k1/d/d). The previous best circuit size lower bounds for this
problem were
nkexp(−O(d)) (due to Beame, Impagliazzo, and Pitassi
[BIP98]) and
nΩ((logk)/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
nO(k2/d)
for this problem (and strengthening our bound even to
nkΩ(1/d)
would require proving that undirected connectivity is not in
NC1.)
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].