1
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Jul 21, 2019 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
    Commented Jul 21, 2019 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
    Commented Jul 21, 2019 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
    Commented Jul 21, 2019 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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