Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

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

share|improve this answer
    
thx, may I get a better bound than $ 2^{\Omega (n^{1/d})} $? –  meshuai 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. –  Kaveh Dec 11 '12 at 5:52
1  
Oh, thx. I need some time to think what you said. And If I have some questions, I will ask you again. thx. –  meshuai 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 –  Sasho Nikolov Dec 11 '12 at 7:12
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). –  Kaveh Dec 11 '12 at 7:34
add comment

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

share|improve this answer
    
Oh, thank you. I need to read the papers first. By the way, it's interesting. –  meshuai Dec 11 '12 at 9:43
2  
Actually, Razborov's original paper was also concerned with the MAJORITY function. –  Kristoffer Arnsfelt Hansen Dec 11 '12 at 11:42
add comment

Your Answer

 
discard

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.