We study maximum selection and sorting of $n$ numbers using imperfect pairwise comparators. The imperfect comparator returns the larger of the two inputs if the inputs are more than a given threshold apart and an adversarially-chosen input otherwise. We consider two adversarial models: a non-adaptive adversary that decides on the outcomes in advance and an adaptive adversary that decides on the outcome of each comparison depending on the previous comparisons and outcomes. Against the non-adaptive adversary, we derive a maximum-selection algorithm that uses at most $2n$ comparisons in expectation and a sorting algorithm that uses at most $2n\ln n$ comparisons in expectation. In the presence of the adaptive adversary, the proposed maximum-selection algorithm uses $\Theta(n\log (1/{\epsilon}))$ comparisons to output a correct answer with probability at least $1-\epsilon$, resolving an open problem in Ajtai et al. (2015). Our study is motivated by a density-estimation problem. Given samples from an unknown distribution, we would like to find a distribution among a known class of $n$ candidate distributions that is close to the underlying distribution in $\ell_1$ distance. Scheffe's algorithm, for example, in Devroye and Lugosi (2001) outputs a distribution at an $\ell_1$ distance at most 9 times the minimum and runs in time $\Theta(n^2\log n)$. Using our algorithm, the runtime reduces to $\Theta(n\log n)$.

Estimating the number of defective elements of a set has various biological applications including estimating the prevalence of a disease or disorder. Group testing has been shown to be more efficient than scrutinizing each element separately for defectiveness. In group testing, we query a subset of elements and the result of the query will be defective if the subset contains at least one defective element. We present an adaptive, randomized group-testing algorithm to estimate the number of defective elements with near-optimal number of queries. Our algorithm uses at most 2 log log d + O(1/δ2log 1/ε) queries and estimates the number of defective elements d up to a multiplicative factor of 1 ± δ, with error probability ≤ ε. Also, we show an information-theoretic lower bound (1 - ε) log log d - 1 on the necessary number of queries any adaptive algorithm makes to estimate the number of defective elements for constant δ.

There has been considerable recent interest in distribution-tests whose run-time and sample requirements are sublinear in the domain-size k. We study two of the most important tests under the conditional-sampling model where each query specifies a subset S of the domain, and the response is a sample drawn from S according to the underlying distribution. For identity testing, which asks whether the underlying distribution equals a specific given distribution or ε-differs from it, we reduce the known time and sample complexities from \widetilde\mathcalO(ε^-4) to \widetilde\mathcalO(ε^-2), thereby matching the information theoretic lower bound. For closeness testing, which asks whether two distributions underlying observed data sets are equal or different, we reduce existing complexity from \widetilde\mathcalO(ε^-4 \log^5 k) to an even sub-logarithmic \widetilde\mathcalO(ε^-5 \log \log k) thus providing a better bound to an open problem in Bertinoro Workshop on Sublinear Algorithms (Fisher, 2014).

English words and the outputs of many other natural processes are well-known to follow a Zipf distribution. Yet this thoroughly-established property has never been shown to help compress or predict these important processes. We show that the expected redundancy of Zipf distributions of order α > 1 is roughly the 1/α power of the expected redundancy of unrestricted distributions. Hence for these orders, Zipf distributions can be better compressed and predicted than was previously known. Unlike the expected case, we show that worst-case redundancy is roughly the same for Zipf and for unrestricted distributions. Hence Zipf distributions have significantly different worst-case and expected redundancies, making them the first natural distribution class shown to have such a difference.

We consider the problems of sorting and maximum-selection of n elements using adversarial comparators. We derive a maximum-selection algorithm that uses 8n comparisons in expectation, and a sorting algorithm that uses 4n log2n comparisons in expectation. Both are tight up to a constant factor. Our adversarial-comparator model was motivated by the practically important problem of density-estimation, where we observe samples from an unknown distribution, and try to determine which of n known distributions is closest to it. Existing algorithms run in Ω(n2) time. Applying the adversarial comparator results, we derive a density-estimation algorithm that runs in only O(n) time.

We consider universal compression of n samples drawn independently according to a monotone or m-modal distribution over k elements. We show that for all these distributions, the per-sample redundancy diminishes to 0 if k = exp(o(n/log n)) and is at least a constant if k = exp(Ω(n)).

Poisson sampling is a method for eliminating dependence among symbols in a random sequence. It helps improve algorithm design, strengthen bounds, and simplify proofs. We relate the redundancy of fixed-length and Poisson-sampled sequences, use this result to derive a simple formula for the redundancy of general envelope classes, and apply this formula to obtain simple and tight bounds on the redundancy of power-law and exponential envelope classes, in particular answering a question posed in [1] about power-law envelopes.

Outlier detection is the problem of finding a few different distributions in a set of mostly identical ones. Closeness testing is the problem of deciding whether two distributions are identical or different. We relate the two problems, construct a sub-linear generalized closeness test for unequal sample lengths, and use this result to derive a sub-linear universal outlier detector. We also lower bound the sample complexity of both problems.

We propose a test that takes random samples drawn from a monotone distribution and decides whether or not the distribution is uniform. The test is nearly optimal in that it uses at most O(n\sqrt\log n) samples, where n is the number of samples that a genie who knew all but one bit about the underlying distribution would need for the same task. Furthermore, we show that any such test would require Ω(n\sqrt\log n) samples for some distributions.

Via a unified viewpoint of probability estimation, classification,and prediction, we derive a uniformly-optimal combined-probability estimator, construct a classifier that uniformly approaches the error of the best possible label-invariant classifier, and improve existing results on pattern prediction and compression.

Over the past decade, several papers, e.g., [1-7] and references therein, have considered universal compression of sources over large alphabets, often using patterns to avoid infinite redundancy. Improving on previous results, we prove tight bounds on expected- and worst-case pattern redundancy, in particular closing a decade-long gap and showing that the worst-case pattern redundancy of i.i.d. distributions is Θ(n1/3)†.

We consider two related problems of estimating properties of a collection of point processes: estimating the multiset of parameters of continuous-time Poisson processes based on their activities over a period of time t, and estimating the multiset of activity probabilities of discrete-time Bernoulli processes based on their activities over n time instants. For both problems, it is sufficient to consider the observations' profile - the multiset of activity counts, regardless of their process identities. We consider the profile maximum likelihood (PML) estimator that finds the parameter multiset maximizing the profile's likelihood, and establish some of its competitive performance guarantees. For Poisson processes, if any estimator approximates the parameter multiset to within distance ε with error probability δ, then PML approximates the multiset to within distance 2ε with error probability at most δ · e4√t·S, where S is the sum of the Poisson parameters, and the same result holds for Bernoulli processes. In particular, for the L1distance metric, we relate the problems to the long-studied distribution-estimation problem and apply recent results to show that the PML estimator has error probability e-(t·S)0.9for Poisson processes whenever the number of processes is k = O(tS log(tS)), and show a similar result for Bernoulli processes. We also show experimental results where the EM algorithm is used to compute the PML.

In the query model of multi-variate function computation, the values of the variables are queried sequentially, in an order that may depend on previously revealed values, until the function's value can be determined. The function's computation query complexity is the lowest expected number of queries required by any query order. Instead of computation, it is often easier to consider verification, where the value of the function is given and the queries aim to verify it. The lowest expected number of queries necessary is the function's verification query complexity. We show that for all symmetric functions of independent binary random variables, the computation and verification complexities coincide. This provides a simple method for finding the query complexity and the optimal query order for computing many functions. We also show that if the symmetry condition is removed, there are functions whose verification complexity is strictly lower than their computation complexity, and mention that the same holds when the independence or binary conditions are removed.