17
$\begingroup$

Blum's $3n-o(n)$ lower bound is the best known circuit lower bound over the complete basis for an explicit function $f : \{0,1\}^n \to \{0,1\}$, cf. Jukna's answer to this question for related results.

What are the best known lower bounds if the range of $f$ is $\{0,1\}^m$? In particular, do we get anything better for $m = n$, or for $m = 2$?

$\endgroup$
18
$\begingroup$

According to the paper A $5n − o(n)$ Lower Bound on the Circuit Size over $U_2$ of a Linear Boolean Function by Kulikov, Melanich, and Mihajlin, when $m=o(n)$ there are no lower bounds known better than $3n - o(n)$. It also outlines a method for obtaining functions for which a $4n - o(n)$ lower bound holds, when $m=n$, based on a result of Lamagne and Savage.

$\endgroup$
11
$\begingroup$

here are new results on this said to be the 1st in ~3 decades and some brief commentary

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.