<p>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. </p>

<p>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.</p>

<p>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).</p>

CC BY-SA 3.0
2012-12-11T05:37:34.367Z
thx, may I get a better bound than $ 2^{\Omega (n^{1/d})} $?
MarshalSHI
CC BY-SA 3.0
2012-12-11T05:52:22.303Z
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.
Kaveh
CC BY-SA 3.0
2012-12-11T06:05:42.690Z
Oh, thx. I need some time to think what you said. And If I have some questions, I will ask you again. thx.
MarshalSHI
CC BY-SA 3.0
2012-12-11T07:12:40.840Z
a lower bound for even approximating majority, and even with unbounded fan-in parity gates allowed, should follow from razborov-smolensky
Sasho Nikolov
CC BY-SA 3.0
2012-12-11T07:34:48.283Z
@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).
Kaveh
CC BY-SA 3.0
2012-12-11T05:25:20.673Z
2012-12-11T05:53:06.950Z
2012-12-11T05:53:06.950Z
Kaveh
<p>The original paper by Smolensky, <em>On Representations by Low-Degree Polynomials</em>, actually contains a direct lower bound on majority. You can have a look at the <a href="http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00366874">original paper</a> (behind a paywall) or at <a href="http://www.cs.toronto.edu/~yuvalf/Smolensky.pdf">this writeup</a>. 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)}}$.</p>

<p>The state-of-the-art might well be <a href="http://www.cs.gunma-u.ac.jp/~amano/paper/icalp_cr.pdf">Amano's paper</a> for the upper bound, <a href="http://www.cs.cmu.edu/~odonnell/papers/approx-by-dnf.pdf">O'Donnell and Wimmer</a> 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)}))$.</p>

CC BY-SA 3.0
2012-12-11T09:43:29.070Z
Oh, thank you. I need to read the papers first. By the way, it's interesting.
MarshalSHI
CC BY-SA 3.0
2012-12-11T11:42:20.160Z
Actually, Razborov's original paper was also concerned with the MAJORITY function.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-12-11T08:33:41.403Z
2012-12-11T08:33:41.403Z
Yuval Filmus
<p>If a circuit ({AND OR NOT} circuit) with depth <em>d</em> computes the majority function,<br> what's the best lower bound for majority function?
<br><br>I know the lower bound for parity function is $ 2^{\Omega (n^{1/d})} $</p>

<cc.complexity-theory><lower-bounds>
lower bound of majority function?
MarshalSHI
# lower bound of majority function?

(Asked by: username_0 on 2012-12-11)

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})} $

**Tags:** cc.complexity-theory, lower-bounds


---

## 2 answers

### Answer by username_1 on 2012-12-11. Score: 10

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).

> **Comments:**
> **username_0**: thx, may I get a better bound than $ 2^{\Omega (n^{1/d})} $?  
> **username_1**: 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.  
> **username_0**: Oh, thx. I need some time to think what you said. And If I have some questions, I will ask you again. thx.  
> **username_2**: a lower bound for even approximating majority, and even with unbounded fan-in parity gates allowed, should follow from razborov-smolensky  
> **username_1**: @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).  

---

### Answer by username_3 on 2012-12-11. Score: 10

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](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00366874) (behind a paywall) or at [this writeup](http://www.cs.toronto.edu/~yuvalf/Smolensky.pdf). 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](http://www.cs.gunma-u.ac.jp/~amano/paper/icalp_cr.pdf) for the upper bound, [O'Donnell and Wimmer](http://www.cs.cmu.edu/~odonnell/papers/approx-by-dnf.pdf) 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)}))$.

> **Comments:**
> **username_0**: Oh, thank you. I need to read the papers first. By the way, it's interesting.  
> **username_4**: Actually, Razborov's original paper was also concerned with the MAJORITY function.  

---

