Some tradeoff lower bounds in the theory of computing.
详细信息
文摘
We investigate the tradeoffs between various resources of computational models. In particular, we study space-approximation tradeoffs in data stream model and time-space tradeoffs in branching program model.;In the data stream model, we are interested in the problem of approximating the Lp distance between two integer vectors of length d, where the Lp distance (p > 0) is defined by ρ p(x, y) = &parl0;ixi -yip&parr0; 1p . For the Lp distance where p ∈ [1, 2], algorithms that use polylogarithmic space in d with approximate factor arbitrarily close to 1 are well-known. In contrast to the case when p ∈ [1, 2], we show that there are no efficient algorithms for the case p > 2. Specifically, we show that any algorithm that approximates the Lp distance for p > 2/(1 ? 4δ) within a factor of dδ in the data stream model requires W&parl0;d1-2p-4d &parr0; space. This is optimal up to polylogarithmic factors for L∞ distance.;In the branching program model, we investigate the problem of time-space tradeoff lower bound for randomized computation. We extend and improve the previous results by Beame, Jayram, and Saks [BST98, BJS01] and by Ajtai [Ajt98, Ajt99a, Ajt99b] in two directions: (1) we extend their lower bounds to randomized computation; (2) we quantitatively improve the lower bounds obtained by Ajtai for boolean branching programs. Specifically, we show that any branching program of subexponential size must have length at least W&parl0;nlognlog logn&parr0; , while Ajtai's analysis implicitly shows a bound of Ω( n log log n/log log log n). The techniques used in our proofs include discrete probability methods and combinatorics.;In addition to results on tradeoff lower bounds, we study explicit constructions of interpolation sets. Using perfect hash families, we use a variant of Indyk's method in [Indyk99] to give an explicit construction of interpolation sets of size O(k 10 log n log log n/log log log n) for the family of boolean functions on n variables which depend symmetrically on at most k variables. Our construction is better than that of [Indyk99] in the case when k is much smaller compared to log n. The n term in the size bound of our construction is very close to the optimum as there is a lower bound of Ω(k2 log n /log k) on the size.