Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
isnt this paper studying that? On the One-Way Function Candidate Proposed by Goldreich Cook et al – vzn Mar 6 '14 at 16:44
up vote 18 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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