  One of the prominent current challenges in complexity theory is the attempt
to prove lower bounds for $TC^0$, the class of constant-depth, polynomial-size
circuits with majority gates. Relying on the results of Williams (2013), an
appealing approach to prove such lower bounds is to construct a non-trivial
derandomization algorithm for $TC^0$. In this work we take a first step towards
the latter goal, by proving the first positive results regarding the
derandomization of $TC^0$ circuits of depth $d>2$.
  Our first main result is a quantified derandomization algorithm for $TC^0$
circuits with a super-linear number of wires. Specifically, we construct an
algorithm that gets as input a $TC^0$ circuit $C$ over $n$ input bits with
depth $d$ and $n^{1+\exp(-d)}$ wires, runs in almost-polynomial-time, and
distinguishes between the case that $C$ rejects at most $2^{n^{1-1/5d}}$ inputs
and the case that $C$ accepts at most $2^{n^{1-1/5d}}$ inputs. In fact, our
algorithm works even when the circuit $C$ is a linear threshold circuit, rather
than just a $TC^0$ circuit (i.e., $C$ is a circuit with linear threshold gates,
which are stronger than majority gates).
  Our second main result is that even a modest improvement of our quantified
derandomization algorithm would yield a non-trivial algorithm for standard
derandomization of all of $TC^0$, and would consequently imply that
$NEXP\not\subseteq TC^0$. Specifically, if there exists a quantified
derandomization algorithm that gets as input a $TC^0$ circuit with depth $d$
and $n^{1+O(1/d)}$ wires (rather than $n^{1+\exp(-d)}$ wires), runs in time at
most $2^{n^{\exp(-d)}}$, and distinguishes between the case that $C$ rejects at
most $2^{n^{1-1/5d}}$ inputs and the case that $C$ accepts at most
$2^{n^{1-1/5d}}$ inputs, then there exists an algorithm with running time
$2^{n^{1-\Omega(1)}}$ for standard derandomization of $TC^0$.
