Person:

Nelson, Jelani

The ℓ1-distance, also known as the Manhattan or taxicab distance, between two vectors x, y in R n is Pn |xi − yi|. i=1 Approximating this distance is a fundamental primitive on massive databases, with applications to clustering, nearest neighbor search, network monitoring, regression, sampling, and support vector machines. We give the first 1-pass streaming algorithm for this problem in the turnstile model with O ∗ (ε −2) space and O ∗ (1) update time. The O ∗ notation hides polylogarithmic factors in ε, n, and the precision required to store vector entries. All previous algorithms either required Ω(ε −3) space or Ω(ε −2) update time and/or could not work in the turnstile model (i.e., support an arbitrary number of updates to each coordinate). Our bounds are optimal up to O ∗ (1) factors.

For an n-variate degree-2 real polynomial p, we prove that (E_{x\sim D}[sig(p(x))]) Is determined up to an additive (\epsilon) as long as D is a k-wise Independent distribution over ({-1, 1}^n) for (k = poly(1/\epsilon)). This gives a broad class of explicit pseudorandom generators against degree-2 boolean threshold functions, and answers an open question of Diakonikolas et al. (FOCS 2009).

Let (\Phi \in \mathbb{R}^{m×n}) be a sparse Johnson-Lindenstrauss transform [KN14] with s non-zeroes per column. For a subset T of the unit sphere, (\epsilon \in (0,1/2)) given, we study settings for m,s required to ensure (\underset {\Phi_{x \in T}} {\mathbb{E} sup} \mid || \Phi x ||^2_2 - 1 \mid < \epsilon), i.e.\ so that (\Phi) preserves the norm of every (x \in T) simultaneously and multiplicatively up to (1+\epsilon). We introduce a new complexity parameter, which depends on the geometry of T, and show that it suffices to choose s and m such that this parameter is small. Our result is a sparse analog of Gordon's theorem, which was concerned with a dense (\Phi) having i.i.d. gaussian entries. We qualitatively unify several results related to the Johnson-Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson-Lindenstrauss transform in numerical linear algebra, classical and model-based compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.

We settle the 1-pass space complexity of ((1 \pm \epsilon))-approximating the (L_p) norm, for real p with 1 ≤ p ≤ 2, of a length-n vector updated in a length-m stream with updates to its coordinates. We assume the updates are integers in the range [–M, M]. In particular, we show the space required is (\Theta(\epsilon^{−2} log(mM) + log log(n))) bits. Our result also holds for 0 < p < 1; although (L_p) is not a norm in this case, it remains a well-defined function. Our upper bound improves upon previous algorithms of [Indyk, JACM ‘06] and [Li, SODA ‘08]. This improvement comes from showing an improved derandomization of the (L_p) sketch of Indyk by using k-wise independence for small k, as opposed to using the heavy hammer of a generic pseudorandom generator against space-bounded computation such as Nisan's PRG. Our lower bound improves upon previous work of [Alon-Matias-Szegedy, JCSS ‘99] and [Woodruff, SODA ‘04], and is based on showing a direct sum property for the 1-way communication of the gap-Hamming problem.

In experimental psychology, the method of paired comparisons was proposed as a means for ranking preferences amongst n elements of a human subject. The method requires performing all (n2) comparisons then sorting elements according to the number of wins. The large number of comparisons is performed to counter the potentially faulty decision-making of the human subject, who acts as an imprecise comparator.

We consider a simple model of the imprecise comparisons: there exists some δ> 0 such that when a subject is given two elements to compare, if the values of those elements (as perceived by the subject) differ by at least δ, then the comparison will be made correctly; when the two elements have values that are within δ, the outcome of the comparison is unpredictable. This δ corresponds to the just noticeable difference unit (JND) or difference threshold in the psychophysics literature, but does not require the statistical assumptions used to define this value.

In this model, the standard method of paired comparisons minimizes the errors introduced by the imprecise comparisons at the cost of (n2) comparisons. We show that the same optimal guarantees can be achieved using 4 n 3/2 comparisons, and we prove the optimality of our method. We then explore the general tradeoff between the guarantees on the error that can be made and number of comparisons for the problems of sorting, max-finding, and selection. Our results provide close-to-optimal solutions for each of these problems.

We give the first L1-sketching algorithm for integer vectors which produces nearly optimal sized sketches in nearly linear time. This answers the first open problem in the list of open problems from the 2006 IITK Workshop on Algorithms for Data Streams. Specifically, suppose Alice receives a vector x ∈ {−M, . . . , M}n and Bob receives y ∈ {−M, . . . , M}n, and the two parties share randomness. Each party must output a short sketch of their vector such that a third party can later quickly recover a (1 ± ε)-approximation to ||x − y||1 with 2/3 probability given only the sketches. We give a sketching algorithm which produces O(ε−2log(1/ε) log(nM))-bit sketches in O(n log2(nM)) time, independent of ε. The previous best known sketching algorithm for L1 is due to [Feigenbaum et al., SICOMP 2002], which achieved the optimal sketch length of O(ε−2log(nM)) bits but had a running time of O(n log(nM)/ε2). Notice that our running time is near-linear for every ε, whereas for sufficiently small values of ε, the running time of the previous algorithm can be as large as quadratic. Like their algorithm, our sketching procedure also yields a small-space, one-pass streaming algorithm which works even if the entries of x, y are given in arbitrary order.

We design efficient data structures for dynamically maintaining a ham-sandwich cut of two point sets in the plane subject to insertions and deletions of points in either set. A ham-sandwich cut is a line that simultaneously bisects the cardinality of both point sets. For general point sets, our first data structure supports each operation in O(n1/3+ε) amortized time and O(n4/3+ε) space. Our second data structure performs faster when each point set decomposes into a small number k of subsets in convex position: it supports insertions and deletions in O(logn) time and ham-sandwich queries in O(klog4n) time. In addition, if each point set has convex peeling depth k , then we can maintain the decomposition automatically using O(klogn) time per insertion and deletion. Alternatively, we can view each convex point set as a convex polygon, and we show how to find a ham-sandwich cut that bisects the total areas or total perimeters of these polygons in O(klog4n) time plus the O((kb)polylog(kb)) time required to approximate the root of a polynomial of degree O(k) up to b bits of precision. We also show how to maintain a partition of the plane by two lines into four regions each containing a quarter of the total point count, area, or perimeter in polylogarithmic time.

We conclude a sequence of work by giving near-optimal sketching and streaming algorithms for estimating Shannon entropy in the most general streaming model, with arbitrary insertions and deletions. This improves on prior results that obtain suboptimal space bounds in the general model, and near-optimal bounds in the insertion-only model without sketching. Our high-level approach is simple: we give algorithms to estimate Renyi and Tsallis entropy, and use them to extrapolate an estimate of Shannon entropy. The accuracy of our estimates is proven using approximation theory arguments and extremal properties of Chebyshev polynomials, a technique which may be useful for other problems. Our work also yields the best-known and near-optimal additive approximations for entropy, and hence also for conditional entropy and mutual information.

In the set cover problem we are given a collection of m sets whose union covers [n]=1n and must find a minimum-sized subcollection whose union still covers [n]. We investigate the approximability of set cover by an approximation ratio that depends only on m and observe that, for any constant c12 , set cover cannot be approximated to within O(2log1−1(loglogm)cm) unless SAT can be decided in slightly subexponential time. The main ingredients in the observation are the (logn) hardness of approximation proof of Lund and Yannakakis and a hardness result for label cover due to Dinur and Safra.

A streaming B-tree is a dictionary that efficiently implements insertions and range queries. We present two cache-oblivious streaming B-trees, the shuttle tree, and the cache-oblivious lookahead array (COLA). For block-transfer size B and on N elements, the shuttle tree implements searches in optimal (O(log_{B+1}N)) transfers, range queries of L successive elements in optimal (O(log_{B+1}N +L/B)) transfers, and insertions in (O((log_{B+1}N)/B^{\Theta(1/(log log B)^2)}+(log^2N)/B)) transfers, which is an asymptotic speedup over traditional B-trees if (B ≥ (log N)^{1+c log log log^2 N}) for any constant c >1. A COLA implements searches in O(log N) transfers, range queries in O(log N + L/B) transfers, and insertions in amortized O((log N)/B) transfers, matching the bounds for a (cache-aware) buffered repository tree. A partially deamortized COLA matches these bounds but reduces the worst-case insertion cost to O(log N) if memory size (M = \Omega(log N)). We also present a cache-aware version of the COLA, the lookahead array, which achieves the same bounds as Brodal and Fagerberg's (cache-aware) (B^{\epsilon})-tree. We compare our COLA implementation to a traditional B-tree. Our COLA implementation runs 790 times faster for random insertions, 3.1 times slower for insertions of sorted data, and 3.5 times slower for searches.