  Proving super-polynomial size lower bounds for $\textsf{TC}^0$, the class of
constant-depth, polynomial-size circuits of Majority gates, is a notorious open
problem in complexity theory. A major frontier is to prove that $\textsf{NEXP}$
does not have poly-size $\textsf{THR} \circ \textsf{THR}$ circuit (depth-two
circuits with linear threshold gates).
  In recent years, R.~Williams proposed a program to prove circuit lower bounds
via improved algorithms. In this paper, following Williams' framework, we show
that the above frontier question can be resolved by devising slightly faster
algorithms for several fundamental problems:
  1. Shaving Logs for $\textsf{$\ell_2$-Furthest-Pair}$. An $n^2
\textrm{poly}(d) / \log^{\omega(1)} n$ time algorithm for
$\textsf{$\ell_2$-Furthest-Pair}$ in $\mathbb{R}^d$ for polylogarithmic $d$
implies $\textsf{NEXP}$ has no polynomial size $\textsf{THR} \circ
\textsf{THR}$ circuits. The same holds for Hopcroft's problem,
$\textsf{Bichrom.-$\ell_2$-Closest-Pair}$ and Integer $\textsf{Max-IP}$.
  2. Shaving Logs for Approximate $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$. An
$n^2 \textrm(d) / \log^{\omega(1)} n$ time algorithm for $(1+1/\log^{\omega(1)}
n)$-approximation to $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$ or
$\textsf{Bichrom.-$\ell_1$-Closest-Pair}$ for polylogarithmic $d$ implies
$\textsf{NEXP}$ has no polynomial size $\textsf{SYM}\circ\textsf{THR}$
circuits.
  3. Shaving Logs for Modest Dimension Boolean $\textsf{Max-IP}$. An $n^2 /
\log^{\omega(1)} n$ time algorithm for Bichromatic Maximum Inner Product with
vector dimension $d = n^\epsilon$ for any small constant $\epsilon$ would imply
$\textsf{NEXP}$ has no polynomial size $\textsf{THR} \circ \textsf{THR}$
circuits. Note there is an $n^2\textrm{polylog}(n)$ time algorithm via fast
rectangle matrix multiplication.
  Our results build on two structure lemmas for threshold circuits.
