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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study maximum selection and sorting of $n$ numbers using pairwisecomparators that output the larger of their two inputs if the inputs are morethan a given threshold apart, and output an adversarially-chosen inputotherwise. We consider two adversarial models. A non-adaptive adversary thatdecides on the outcomes in advance based solely on the inputs, and an adaptiveadversary that can decide on the outcome of each query depending on previousqueries and outcomes.  Against the non-adaptive adversary, we derive a maximum-selection algorithmthat uses at most $2n$ comparisons in expectation, and a sorting algorithm thatuses at most $2n \ln n$ comparisons in expectation. These numbers are withinsmall constant factors from the best possible. Against the adaptive adversary,we propose a maximum-selection algorithm that uses $\Theta(n\log(1/{\epsilon}))$ comparisons to output a correct answer with probability atleast $1-\epsilon$. The existence of this algorithm affirmatively resolves anopen problem of Ajtai, Feldman, Hassadim, and Nelson.  Our study was motivated by a density-estimation problem where, given samplesfrom an unknown underlying distribution, we would like to find a distributionin a known class of $n$ candidate distributions that is close to underlyingdistribution in $\ell_1$ distance. Scheffe's algorithm outputs a distributionat an $\ell_1$ distance at most 9 times the minimum and runs in time$\Theta(n^2\log n)$. Using maximum selection, we propose an algorithm with thesame approximation guarantee but run time of $\Theta(n\log n)$.

Maximum Selection and Sorting with Adversarial Comparators and an Application to Density Estimation