Theory of Computing
-------------------
Title     : Lower Bound Techniques in the Comparison-Query Model and Applications to Inversion Minimization
Authors   : Ivan Hu, Dieter van Melkebeek, and Andrew Morgan
Volume    : 20
Number    : 7
Pages     : 1-62
URL       : https://theoryofcomputing.org/articles/v020a007

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

  * [(a)] $\log_2((\alpha(1-\alpha)n)!) - O(\log n)$ queries are needed
         whenever the tree has a subtree that contains a fraction $\alpha$
	 of the leaves. This implies a lower bound of
	 $\log_2((\frac{k}{(k+1)^2}n)!) - O(\log n)$ for trees of degree $k$. 
  * [(b)] $\log_2(n!) - O(\log n)$ queries are needed in case the tree is binary. 
  * [(c)] $\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 new techniques for
any problem $\Pi$ 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,\dots,n)$. Consider the subgraph
consisting of the edges between vertices with the same value under
$\Pi$. We show that the size of any decision tree for $\Pi$ must be at
least

  * [(i)] the number of connected components of this subgraph, and 
  * [(ii)] the factorial (or Gamma function) 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 appear in the
literature as the coefficients of polynomials formed by the Gaussian
binomial coefficients, also known as Gaussian polynomials.

-----------------

A conference version of this paper appeared in the Proceedings of 
the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA'23).