Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PARTIAL ORDERS:
Reports tagged with Partial orders:
TR10-027 | 28th February 2010
Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant

#### Testing monotonicity of distributions over general partial orders

We investigate the number of samples required for testing the monotonicity of a distribution with respect to an arbitrary underlying partially ordered set. Our first result is a nearly linear lower bound for the sample complexity of testing monotonicity with respect to the poset consisting of a directed perfect matching. ... more >>>

TR20-096 | 22nd June 2020
Igor Sergeev

#### On the asymptotic complexity of sorting

We investigate the number of pairwise comparisons sufficient to sort \$n\$ elements chosen from a linearly ordered set. This number is shown to be \$\log_2(n!) + o(n)\$ thus improving over the previously known upper bounds of the form \$\log_2(n!) + \Theta(n)\$. The new bound is achieved by the proposed group ... more >>>

ISSN 1433-8092 | Imprint