Function Computation with Optimal Number of Queries

Evaluating a multivariate function is a crucial and ubiquitous task whose importance has inspired countless different computational models. These models are made by restricting the function's class, changing the computational elements, moderating the computation error probability, adding assumptions on input probabilities, assuming noisy queries, etc. In most function-computation problems, the major cost of calculating the function is the price of samples or queries. The query meaning may change from one model to another but the aspiration to minimize the number of queries is unavoidable in all the models. In this dissertation, we consider and optimize the number of queries for two models in Part I and II. In part I, we study maximum selection and sorting of n numbers using pairwise comparators that output the larger of their two inputs if the inputs are more than a given threshold apart, and output an adversarially-chosen input otherwise. We consider two adversarial models. A non-adaptive adversary that decides on the outcomes in advance based solely on the inputs, and an adaptive adversary that can decide on the outcome of each query depending on previous queries 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. These numbers are within small 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 at least 1 -- epsilon. The existence of this algorithm affirmatively resolves an open problem in [5]. Our study was motivated by a density-estimation problem where, given samples from an unknown underlying distribution, we would like to find a distribution in a known class of n candidate distributions that is close to underlying distribution in l1 distance. Scheffe's algorithm [19] outputs a distribution at an l₁ distance at most 9 times the minimum and runs in time [Theta](n2 log n). Using maximum selection, we propose an algorithm with the same approximation guarantee but run time [Theta](n log n). In Part II, we consider and propose a new method for function computation. 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 optimal query order for computing many functions. We also show that after relaxing any of the symmetry, independence, or binary inputs restrictions, there are functions whose verification complexity is strictly lower than their computation complexit