Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-086 | 2nd June 2011 02:41

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

RSS-Feed




TR11-086
Authors: Masaki Yamamoto
Publication: 2nd June 2011 03:08
Downloads: 3990
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