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

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

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