Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees

Authors: I. Hu, D. van Melkebeek, and A. Morgan
Reference: Theory of Computing, 20(7): 1-62, 2024.
Earlier versions:
- 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.

Abstract

Given a rooted tree and a ranking of its leaves, what is the minimum number of inversions of the leaves that can be attained by ordering the tree? This variation of the well-known problem of counting inversions in arrays originated in mathematical psychology. It has the evaluation of the Mann-Whitney statistic for detecting differences between distributions as a special case.

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₂(n!) for sorting n items. For trees with n leaves we show, in increasing order of closeness to the sorting lower bound:

log₂((α(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₂((k/(k+1)² n)!) - O(log n) for trees of degree k.
log₂(n!) - O(log n) queries are needed in case the tree is binary.
log₂(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.

Lower bounds on query complexity then follow by taking the base-2 logarithm. Technique (i) represents a discrete analog of a classical technique in algebraic complexity and allows us to establish (c) and a tight lower bound for counting cross inversions, as well as unify several of the known lower bounds in the comparison-query model. Technique (ii) represents an analog of sensitivity arguments in Boolean complexity and allows us to establish (a) and (b).

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