Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CIRCUIT SIZE:
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 >>>

TR20-005 | 17th January 2020
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

#### Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

Revisions: 1

We provide a tight characterisation of proof size in resolution for quantified Boolean formulas (QBF) by circuit complexity. Such a characterisation was previously obtained for a hierarchy of QBF Frege systems (Beyersdorff & Pich, LICS 2016), but leaving open the most important case of QBF resolution. Different from the Frege ... more >>>

ISSN 1433-8092 | Imprint