I am trying to show the existence of a polynomial size, bounded depth monotone circuit on the inputs $(x_1,\ldots, x_n)$ that gives $1$ if $\sum x_i \geq n/2 + n/\log n$ and $0$ if $\sum x_i \leq n/2 - n/\log n$. This is a modified form of the MAJORITY problem.

I want to use the probabilistic method but I cant seem to get it to work. I found a way to get a circuit that was not of bounded depth, iterate a bunch of random layers of gates that compute the MAJORITY function for three randomly selected inputs. This will, for $\mathcal{O}(\log n)$ depth, give the right result with overwhelming probability, so one such circuit is always correct.

I think I should have layers of alternating AND and OR gates, but since the $n/\log n$ factor is so small, even when we should get a $1$ for instance, the probability that a random input is a $1$ is only $1/2 + 1/\log n$, not really so high. I cannot seem to amplify this enough to take care of both cases.

Any help?


This task is known as approximate counting or approximate majority. The first to construct such a circuit was Ajtai in his celebrated 1983 paper $\Sigma_1^1$-formulae on finite structures, which also proves the first switching lemma. You can check out Section 3 for the construction. For a more modern account, see Section 2 of Viola's Randomness buys depth for approximate counting.

  • $\begingroup$ Thanks, these papers are going a bit above my head I am afraid. However, from reading some of Viola's paper, isn't he actually saying in the abstract that this problem cannot be solved in depth $2$ polysize circuits, but this does not concern me as the depth should be bounded but may be large? $\endgroup$ – Slugger Jul 21 '19 at 23:33
  • $\begingroup$ Section 2.1 of Viola's paper gives a construction for $n/2 \pm n/\log^{d-1}n$, which uses depth $d$. $\endgroup$ – Yuval Filmus Jul 21 '19 at 23:36
  • $\begingroup$ You could try using the keywords "approximate counting" or "approximate majority" to find other expositions of this construction. I'm afraid all constructions would be somewhat technical. $\endgroup$ – Yuval Filmus Jul 21 '19 at 23:37
  • $\begingroup$ Thanks for the replies! My knowledge is more in the areas of combinatorics and graph theory and not so much theoretical computer science so I am not really familiar with much of the terminology in these papers. Anyway, I will have a look :) $\endgroup$ – Slugger Jul 21 '19 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.