English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Given a rooted tree and a ranking of its leaves, what is the minimum numberof inversions of the leaves that can be attained by ordering the tree? Thisvariation of the problem of counting inversions in arrays originated inmathematical psychology, with the evaluation of the Mann--Whitney statistic fordetecting differences between distributions as a special case.  We study the complexity of the problem in the comparison-query model, usedfor problems like sorting and selection. For many types of trees with $n$leaves, we establish lower bounds close to the strongest known in the model,namely the lower bound of $\log_2(n!)$ for sorting $n$ items. We show:  (a) $\log_2((\alpha(1-\alpha)n)!) - O(\log n)$ queries are needed wheneverthe tree has a subtree that contains a fraction $\alpha$ of the leaves. Thisimplies a lower bound of $\log_2((\frac{k}{(k+1)^2}n)!) - O(\log n)$ for treesof 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 oftrees of degree $k$, including perfect trees with even $k$.  The lower bounds are obtained by developing two novel techniques for ageneric problem $\Pi$ in the comparison-query model and applying them toinversion minimization on trees. Both techniques can be described in terms ofthe Cayley graph of the symmetric group with adjacent-rank transpositions asthe generating set. Consider the subgraph consisting of the edges betweenvertices with the same value under $\Pi$. We show that the size of any decisiontree for $\Pi$ must be at least:  (i) the number of connected components of this subgraph, and  (ii) 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.

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