Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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$?
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.
here are new results on this said to be the 1st in ~3 decades and some brief commentary
A better-than-3n lower bound for the circuit complexity of an explicit function / Find, Golovnev, Hirsch, Kulikov
We consider Boolean circuits over the full binary basis. We prove a $(3+\frac{1}{86})n−o(n)$ lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the $3n−o(n)$ bound of Norbert Blum (1984).
Better Circuit Lower Bounds for Explicit Functions / Ilya Razenshteyn, MIT CSAIL student blog
