Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Circuit Size:
TR02-012 | 3rd February 2002
Ran Raz

On the Complexity of Matrix Product

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

TR05-032 | 16th March 2005
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen

Reviewing Bounds on the Circuit Size of the Hardest Functions

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

ISSN 1433-8092 | Imprint