Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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