Reviews

Reviews for the paper “Computing majority with low-fan-in majority queries”:

First reviewer

1: (weak accept)

The paper deals with the following problem: what is the complexity of computing the Majority function on n bits with Majority gates of fan-in << n? Formally, consider a depth-2 Boolean circuit made up of Majority gates that take at most k variables as input. What is the least k for which such a circuit can compute the Majority function on n bits?

While the formal study of this problem was initiated by Kulikov and Podolskii [KP] recently (STACS 2017), non-trivial bounds for similar problems have been used in many other results in complexity theory. (See KP for references)

Here the author proves the following results for this problem:

  1. The first non-trivial upper bound for depth 2 circuits: It is shown that there is a depth-2 circuit for Maj_n with k roughly 2n/3. This answers an open question of KP.
  2. A simple proof of a lower bound of n^{2/3}. The author notes that this is simply a special case of a stronger result of KP.

The first of these results is an interesting statement, being the first non-trivial upper bound that holds for all n (previously non-trivial upper bounds were known for some small values of n). The proof is a simple construction. The author mentions that this result was independently discovered by Bruno Bauwens via computer search, but I could not find a paper with this result.

I am not sure what the second result adds, since a stronger result (which is not much harder) is already present in the work of KP.

The author also considers an extension of this model to a "Decision Tree" of k-bit Majority queries. The intuition for this is that the lower bounds above only use the fact that the circuit contains Majority gates at the level just above the variables and hence continue to hold if the output gate is an arbitrary function of fan-in k. This corresponds to a *non-adaptive* DT of depth k. Extending this, an arbitrary DT is considered here.

The author observes that any DT as above must make at least n/k queries (essentially all variables have to be seen by at least one query). Further, the following upper bounds are proved:

  1. If the DT is allowed to make arbitrary threshold queries (i.e. ask if a given subset S of bits has at least t ones for any S,t), then there is DT of depth n log k/k (1+o(1)).
  2. If the DT is allowed to make only strict majority queries (i.e. ask if a given subset S of bits has more ones than zeroes), then there is DT of depth 2n log k/k (1+o(1)). The construction furthermore seems to yield roughly n log k/k as long as k << n.

Thus, the lower and upper bounds are off by a log k factor.

While I did not find the above results very interesting, I did like the problem of understanding the DT depth of Majority in this model. Perhaps this will lead to some interesting work in the future.

SUMMARY: Overall, the principal result is interesting because of the applicability of the problem in complexity theory. The latter results are not so interesting for me, but the problem statement is nice. Based on this, I would recommend a weak accept.

Second reviewer

1: (weak accept)

The paper studies whether MAJORITY of n bits can be computing by depth-2 circuits of the form MAJ_k (MAJ_k). This question has been studies before. Here the main contribution is that it is possible to do above with k < 2n/3+O(1). This has been explicitly asked in the previous work [6].

PROs:

  • the upper bound of k<=2n/3+O(1) is interesting, new, and non-trivial.
  • paper also looks at the adaptive setting, where a better bound is proven: ~n/k bottom gates are needed if the top one is MAJ_k.

CONs:

  • the problem has better answers for randomized algorithms (which is the focus of [6]). In fact [6] showed that randomized algorithms (where k~=n^{2/3} is achievable and best possible) are provable better than deterministic ones (where k>=n^{13/19}).
  • the deterministic n^{2/3} is not that new: it essentially follows the proof of n^{2/3} for randomized algorithms in [6].

The author should make the above 2 points much more clear in the writeup.

Third reviewer

1: (weak accept)

This paper studies the problem of computing the n-bit majority function MAJ_n using lower fan-in majorities MAJ_k for k < n. The main result shows that MAJ_n can be computed by a polynomial-size (in fact, linear-size) depth-two circuit of MAJ_k gates for k = 2n/3 + 4. This addresses a question of Kulikov and Podolskii (STACS '17), who proved a lower bound of k >= ~Omega(n^{13/19}), but were unable to prove any non-trivial upper bound of k < n. The present submission also provides a substantially simpler proof of the weaker lower bound k >= Omega(n^{2/3}).

Next, the paper introduces the problem of computing MAJ_n when access to the input is restricted to adaptively chosen queries to MAJ_k gates. Here, the goal is to understand the relationship between k and the number of queries that must be made. It provides nearly matching upper and lower bounds of Omega(n/k) and O((n/k) log k) for this problem.

All of the proofs are quite simple, intuitive, and rely only on first principles. The new adaptive model is natural to consider, and the paper gives a nearly complete solution. While the main contribution is quantitatively minor in comparison to the remaining gap between ~Omega(n^{13/19}) and O(n), it still breaks a conceptual barrier facing prior work on this topic. I believe it would be reasonable to accept this paper if there is room.

Minor comments:

Page 6, line -5: log should be \log