# Polysize bounded depth circuit for modified MAJORITY problem

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.
• 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? – Slugger Jul 21 '19 at 23:33
• Section 2.1 of Viola's paper gives a construction for $n/2 \pm n/\log^{d-1}n$, which uses depth $d$. – Yuval Filmus Jul 21 '19 at 23:36