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})} $
5
$\begingroup$
$\endgroup$
10
$\begingroup$
$\endgroup$
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).
-
$\begingroup$ thx, may I get a better bound than $ 2^{\Omega (n^{1/d})} $? $\endgroup$ – MarshalSHI Dec 11 '12 at 5:37
-
$\begingroup$ 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. $\endgroup$ – Kaveh Dec 11 '12 at 5:52
-
1$\begingroup$ Oh, thx. I need some time to think what you said. And If I have some questions, I will ask you again. thx. $\endgroup$ – MarshalSHI Dec 11 '12 at 6:05
-
$\begingroup$ a lower bound for even approximating majority, and even with unbounded fan-in parity gates allowed, should follow from razborov-smolensky $\endgroup$ – Sasho Nikolov Dec 11 '12 at 7:12
-
1$\begingroup$ @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). $\endgroup$ – Kaveh Dec 11 '12 at 7:34
10
$\begingroup$
$\endgroup$
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)}))$.
answered Dec 11 '12 at 8:33
-
$\begingroup$ Oh, thank you. I need to read the papers first. By the way, it's interesting. $\endgroup$ – MarshalSHI Dec 11 '12 at 9:43
-
2$\begingroup$ Actually, Razborov's original paper was also concerned with the MAJORITY function. $\endgroup$ – Kristoffer Arnsfelt Hansen Dec 11 '12 at 11:42
