- Authors: I. Hu, D. van Melkebeek, and A. Morgan
- Reference: In
*Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms*, pages 2836-2866, 2023. - Versions:
- I. Hu, D. van Melkebeek, and A. Morgan. Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees. arXiv:2211.12441v2, 2024.
- I. Hu, D. van Melkebeek, and A. Morgan.
Query Complexity of Inversion Minimization on Trees.
In
*Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms*, pages 2836-2866, 2023. - I. Hu, D. van Melkebeek, and A. Morgan. Query Complexity of Inversion Minimization on Trees. Electronic Colloquium on Computational Complexity, Technical Report ECCC-TR 22-158, 2022.

We study the complexity of the problem in the comparison-query model, the standard model for problems like sorting, selection, and heap construction. The complexity depends heavily on the shape of the tree: for trees of unit depth, the problem is trivial; for many other shapes, we establish lower bounds close to the strongest known in the model, namely the lower bound of log_{2}(*n*!) for sorting *n* items. For trees with *n* leaves we show, in increasing order of closeness to the sorting lower bound:

- log
_{2}((α(1-α)*n*)!) - O(log*n*) queries are needed whenever the tree has a subtree that contains a fraction α of the leaves. This implies a lower bound of log_{2}((*k*/(*k*+1)^{2}*n*)!) - O(log*n*) for trees of degree*k*. - log
_{2}(*n*!) - O(log*n*) queries are needed in case the tree is binary. - log
_{2}(*n*!) - O(*k*log*k*) queries are needed for certain classes of trees of degree*k*, including perfect trees with even*k*.

The lower bounds are obtained by developing two novel techniques for a generic problem Π in the comparison-query model and applying them to inversion minimization on trees. Both techniques can be described in terms of the Cayley graph of the symmetric group with adjacent-rank transpositions as the generating set, or equivalently, in terms of the edge graph of the permutahedron, the polytope spanned by all permutations of the vector (1,2,...,*n*). Consider the subgraph consisting of the edges between vertices with the same value under Π. We show that the size of any decision tree for Π must be at least:

- the number of connected components of this subgraph, and
- the factorial of the average degree of the complementary subgraph, divided by
*n*.

Along the way to proving (b), we derive a tight upper bound on the maximum probability of the distribution of cross inversions, which is the distribution of the Mann-Whitney statistic in the case of the null hypothesis. Up to normalization the probabilities alternately appear in the literature as the coefficients of polynomials formed by the Gaussian binomial coefficients, also known as Gaussian polynomials.

dieter@cs.wisc.edu