Name
Abstract | ||
|---|---|---|
If k < n, can one express the majority of n bits as the majority of at most k majorities, each of at most k bits? We prove that such an expression is possible only if k greater than or similar to n(4/5) = n(0.8). This improves on a bound proved by Kulikov and Podolskii [Computing majority by constant depth majority circuits with low fan-in gates, in Proceedings of the 34th STACS, Schloss Dagstuhl, Wadern, Germany, 2017, 49], who showed that k greater than or similar to n(0.7+o(1)). Our proof is based on ideas originating in discrepancy theory as well as a strong concentration bound for sums of independent Bernoulli random variables and a strong anticoncentration bound for the hypergeometric distribution. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1137/18M1223599 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
boolean circuits,majority,lower bound | Discrete mathematics,Mathematics | Journal |
Volume | Issue | ISSN |
34 | 1 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Engels | 1 | 10 | 3.95 |
| Mohit Garg | 2 | 0 | 0.34 |
| Kazuhisa Makino | 3 | 1088 | 102.74 |
| Anup Rao | 4 | 581 | 32.80 |