A tighter lower bound on the circuit size of the hardest Boolean functions
Masaki Yamamoto · Electronic colloquium on computational complexity · 2011
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: ( 1 + log n n − c n ) 2 n n ≤ L(n) ≤ ( 1 + 3 log n n + c n ) 2 n n .