Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HARDEST FUNCTION:
Reports tagged with hardest function:
TR11-086 | 2nd June 2011
Masaki Yamamoto

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

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 ... more >>>

ISSN 1433-8092 | Imprint