\documentclass[11pt]{paper}

\setlength{\parindent}{0 pt}
\setlength{\parskip}{1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
%\usepackage{wasysym}
\usepackage[usenames]{color}

\usepackage{enumerate}
\usepackage{cite}
\usepackage{float}
\usepackage{xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand{\mathset}[1]{\ensuremath {\mathbb {#1}}}
\newcommand{\N}{\mathset {N}}
\newcommand{\R}{\mathset {R}}
\newcommand{\Q}{\mathset {Q}}
\newcommand{\Z}{\mathset {Z}}
\newcommand{\EX}{\mathbf {E}}
\newcommand{\script}[1]{\ensuremath{\mathcal {#1}}}
\newcommand{\etal}{\textit {et al.}}
\newcommand{\eps}{\varepsilon}
\newcommand{\eqdef}{:=}
\newcommand{\boruvka}{Bor\r{u}vka}
\newcommand{\wspd}{\texttt{wspd}}
\DeclareMathOperator{\emst}{emst}
\DeclareMathOperator{\conv}{CH}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\DT}{DT}
\DeclareMathOperator{\UC}{UC}
\DeclareMathOperator{\LC}{LC}
\newcommand{\DKL}{D_\textup{KL}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{problem}[theorem]{Problem}
\newtheorem{obs}[theorem]{Beobachtung}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}


\title{The Non-Uniform Hierarchy Theorem}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{The Theorem}
\begin{theorem}[Shannon's theorem]
\label{thm:shannon}
  There exist constants $c_1 \geq 1$ and  $c_2 > 0$ such that
  for all $n \in \N$, 
  (a) every Boolean function $f: \{0, 1\}^n \rightarrow \{0,1\}$
    can be realized by a Boolean circuit of size at most $c_1 2^n/n$;
  and (b) there exists a Boolean function $g: \{0, 1\}^n \rightarrow
    \{0, 1\}$ that cannot be realized by a Boolean circuit of
    size at most $c_2 2^n/n$.
\end{theorem}

\begin{theorem}[Non-uniform Hierarchy Theorem]
There is a constant $c_3 > 0$ such that for any
$T, T': \N \rightarrow \N$ with
$T(n) \leq c_3 T'(n)$ and $T'(n) \leq c_1 2^n/n$, for 
$n \in \N$, there exists a language $L \subseteq \{0, 1\}^*$
such that $L$ that cannot be decided by a circuit family of size at 
most $T(n)$, 
but there is a circuit family of size at most $T'(n)$ that decides $L$.
\end{theorem}

\begin{proof}
Set $c_3 = c_2/2c_1$ and
define $f(n) = \max\{ m \in \N \mid c_1 2^m/m \leq n\}$, for $n \geq 2c_1$.
For any $n \geq 2c_1$ and $m = f(n)$, we have
$c_1 2^m/m > n/2$, because 
\[
n < c_1 \frac{2^{m+1}}{m+1} = \frac{2m}{m+1} c_1 \frac{2^{m}}{m}
< 2 c_1 \frac{2^{m}}{m}.
\]
Now, fix $n \geq 2c_1$ and let $m = f(T'(n))$. By Theorem~\ref{thm:shannon},
there exists a Boolean function $g: \{0, 1\}^m \rightarrow \{0, 1\}$ 
such that $g$ can be realized by a Boolean circuit of size 
$c_12^m/m \leq T'(n)$,
but not by a Boolean circuit of size 
$c_2 2^m/m = (c_2/c_1)c_12^m/m \geq (c_2/2c_1) T'(n) \geq T(n)$.
Furthermore, since $f$ is monotone,
\[
m = f(T'(n)) \leq f(c_1 2^n/n) \leq n.
\]
Thus, we can define a language $L_n \subseteq \{0, 1\}^n$ by
\[
  L_n = \{ w \circ 0^{n-m} \mid w \in \{0, 1\}^m,\, g(w) = 1\}.
\]
Now the language $L = \bigcup_{n \geq 2c_1} L_n$ has the
desired properties.
\end{proof}
\end{document}