__
TR11-086 | 2nd June 2011 02:41
__

#### A tighter lower bound on the circuit size of the hardest Boolean functions

**Abstract:**
In [IPL2005],

Frandsen and Miltersen improved bounds on the circuit size $L(n)$ of the hardest Boolean function on $n$ input bits:

for some constant $c>0$:

\[

\left(1+\frac{\log n}{n}-\frac{c}{n}\right)

\frac{2^n}{n}

\leq

L(n)

\leq

\left(1+3\frac{\log n}{n}+\frac{c}{n}\right)

\frac{2^n}{n}.

\]

In this note,

we announce a modest improvement on the lower bound:

for some constant $c>0$ (and for any sufficiently large $n$),

\[

L(n) \geq

\left(1+2\frac{\log n}{n}-\frac{c}{n}\right)

\frac{2^n}{n}.

\]