  As far as I know, at the time that I originally devised this result (1998),
this was the first constructive proof that, for any integer $k$, there is a
language in $\Sigma_2^P$ that cannot be simulated by a family of logic circuits
of size $n^k$. However, this result had previously been proved
non-constructively: see Cai and Watanabe [CW08] for more information on the
history of this problem.
  This constructive proof is based upon constructing a language $\Gamma$
derived from the satisfiabiility problem, and a language $\Lambda_k$ defined by
an alternating Turing machine. We show that the union of $\Gamma$ and
$\Lambda_k$ cannot be simulated by circuits of size $n^k$.
