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

Ivan Hu, Dieter van Melkebeek, Andrew Morgan

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 problem of…