lower bound of majority function?

If a circuit ({AND OR NOT} circuit) with depth d computes the majority function,
what's the best lower bound for majority function?

I know the lower bound for parity function is $2^{\Omega (n^{1/d})}$

You haven't specified exactly what kind of circuits, but in general since parity $\oplus$ is in $\mathsf{TC^0}$ and majority $Maj$ is complete for $\mathsf{TC^0}$, you get a similar subexponential size lower-bound for majority.

A simple reduction would go through counting function $NumOnes$ that counts the number 1s in the input in binary. This would give $2^{n^{\Omega(1/d)}}$ where constant in the exponent comes from the size of $\mathsf{AC^0}[Maj]$ circuit computing $numones$. I don't know the best value of the constant but it shouldn't be big.

On the other hand, there are $2^{n^{O(1/d)}}$ circuits for majority as majority is in $\mathsf{NC^1}$ and any $\mathsf{NC^1}$ circuits can be converted into a subexponential-size bounded-depth $\mathsf{AC^0}$ circuit (by performing a layered brute-force).

• thx, may I get a better bound than $2^{\Omega (n^{1/d})}$? Dec 11 '12 at 5:37
• I don't think you can get much better, I have updated the answer to explain why. However it might be possible to get a little bit better constants. Dec 11 '12 at 5:52
• Oh, thx. I need some time to think what you said. And If I have some questions, I will ask you again. thx. Dec 11 '12 at 6:05
• a lower bound for even approximating majority, and even with unbounded fan-in parity gates allowed, should follow from razborov-smolensky Dec 11 '12 at 7:12
• @Sasho, yes, I think that is correct, it makes the class of circuits larger ($\mod_q$ gates) and replaces exactly computing majority with approximating it (however it doesn't change the bounds). Dec 11 '12 at 7:34

The original paper by Smolensky, On Representations by Low-Degree Polynomials, actually contains a direct lower bound on majority. You can have a look at the original paper (behind a paywall) or at this writeup. For the converse, it is known that an NC$^1$ circuit of size $S$ can be simulated in AC$_0^d$ in size $2^{S^{1/\Omega(d)}}$. Majority has NC$^1$ circuits of polynomial size, and so you can't get a lower bound better than $2^{n^{1/O(d)}}$.

The state-of-the-art might well be Amano's paper for the upper bound, O'Donnell and Wimmer for the lower bound; the latter use Håstad's switching lemma. According to Amano, the minimum size of a depth $d$ circuit that $\epsilon$-approximates Majority on $n$ variables is $\exp(\Theta(n^{1/(2d-2)}))$.

• Oh, thank you. I need to read the papers first. By the way, it's interesting. Dec 11 '12 at 9:43
• Actually, Razborov's original paper was also concerned with the MAJORITY function. Dec 11 '12 at 11:42