Ran Raz

We prove a lower bound of $\Omega(m^2 \log m)$ for the size of

any arithmetic circuit for the product of two matrices,

over the real or complex numbers, as long as the circuit doesn't

use products with field elements of absolute value larger than 1

(where $m \times m$ is ...
more >>>

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen

In this paper we review the known bounds for $L(n)$, the circuit size

complexity of the hardest Boolean function on $n$ input bits. The

best known bounds appear to be $$\frac{2^n}{n}(1+\frac{\log

n}{n}-O(\frac{1}{n})) \leq L(n) \leq\frac{2^n}{n}(1+3\frac{\log

n}{n}+O(\frac{1}{n}))$$ However, the bounds do not seem to be

explicitly stated in the literature. We ...
more >>>