Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR11-086 | 2nd June 2011 02:41

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

TR11-086
Authors: Masaki Yamamoto
Publication: 2nd June 2011 03:08
Downloads: 1988
Keywords:

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}.$

ISSN 1433-8092 | Imprint