# Circuit complexity of hardest monotone function

Show there exists a monotone function $$f\colon \{0,1\}^n \mapsto \{0,1\}$$, such that the minimal size of a monotone circuit that computes $$f$$ is $$\Omega(2^n / n^2)$$. Use the fact that the number of monotone functions is at least $$2^{\frac{2^n}{2 \sqrt{n}}}$$.

Every monotone $$f\colon \{0,1\}^n \to \{0,1\}$$ has a minimal size monotone circuit $$C_f$$ that computes $$f$$. Since there are at least $$2^{\frac{2^n}{2 \sqrt{n}}}$$ functions such as $$f$$, there are at least $$2^{\frac{2^n}{2 \sqrt{n}}}$$ circuits such as $$C_f$$.

Assume the minimal size of a monotone circuit that implements a monotone function $$f\colon \{0,1\}^n \to \{0,1\}$$ is $$o(2^n / n^2)$$. Fix some $$c\in \mathbb{R}^+$$. There exists some $$N$$, such that for every $$n>N$$ it holds that $$\mathrm{Size}(C_f) \leq c\cdot \frac{2^n}{n^2}$$.

I am trying to show that the number of possible monotone circuits $$C_f$$ on $$n>N$$ inputs - whose size is minimal and bounded by $$c\cdot \frac{2^n}{n^2}$$ - is less than the number of monotone functions $$f$$. This would mean the assumption I made leads to a contradiction, and thus the opposite is true.

Can you help me solve this problem?

• $$f\colon \{0,1\}^n \to \{0,1\}$$ is monotone if for every $$x,y\in \{0,1\}^n$$ such that $$x_i \leq y_i$$ for all $$i$$, it holds that $$f(x) \leq f(y)$$.
• A circuit $$C(x_1,\ldots,x_n)$$ is monotone if it only has AND gates and OR gates.
• Do you know how to show that some function on $n$ bits requires circuits of size $\Omega(2^n/n)$? It is (almost) exactly the same calculation. Oct 25 '20 at 12:04
• I do not, but I'd love to read about that. In particular, how many different boolean circuits exist of a certain size? How does this number change when we also require that the circuits are monotone?
– Ido
Oct 25 '20 at 12:30
• It is extremely strange that someone would ask you to prove an extension of this classical result without explaining first the proof of that classical result. Oct 25 '20 at 12:31
• You can find the proof in many places, for example these lecture notes. Jukna's monograph Boolean function complexity also contains a proof of a refined version of this result, showing that hardest function requires circuits of size $\sim 2^n/n$. Oct 25 '20 at 12:33
• Thanks, I will read the proof.
– Ido
Oct 25 '20 at 14:23