Parallel Functional Arrays. Ananya Kumar, Guy E. Blelloch and Robert Harper. Principles of Programming Languages (POPL) 2017. Accepted with review grades of A/A/A/B/C. Conference acceptance rate was 23%
The goal of this paper is to develop a form of functional/persistent arrays that can be used in parallel. We allow operations on “old” arrays to be more expensive than on “new” arrays. The key difficulty is 1. Providing a functional interface while safely dealing with concurrent effects under the hood, and 2. Giving a deterministic way to bound the costs even though the actual costs depend on the interleaving of execution threads.
Advised by Guy Blelloch and Bob Harper.
SCS Alumni Award for Undergraduate Excellence, and second place in Math Competition at Meeting of the Minds 2017.
Given a set of points P, an approximate convex hull is a subset of points in P that approximately covers the original set. More formally, every point in P is within distance epsilon from the convex closure of the subset. The optimal approximate convex hull is the smallest such subset. Approximate convex hulls are intimately tied to the notion of coresets, which are used in computational geometry, machine learning, and approximation algorithms.
Existing streaming (one-pass) algorithms for this problem give bounds that only depend on epsilon but that ignore the structure of the data. A natural question is whether we can do better than state-of-the-art when the data is well structured, in particular, when the optimal approximate convex hull is small.
We show lower bounds for this problem to justify that it is hard. We then propose two interesting relaxations of the problem. In the first relaxation the data is randomly permuted before the algorithm runs. In the second relaxation our approximation only needs to be correct in “most” directions. We come up with new streaming algorithms and theorems for these relaxations.
Advised by Avrim Blum and collaborated with Lin Yang, Harry Lang, Vladimir Braverman.