Our aim is to approximate the boundary of a set of points, when the number of points is too large to fit into computer memory. In particular, we are interested in streaming algorithms: algorithms that compute the approximate convex hull in one pass, and use a small amount of memory. These algorithms have potential applications in data analysis, computer graphics, and unsupervised learning (because approximate convex hulls can be used as a sparse dictionary). We devise lower bounds and algorithms for this problem.
I was very honored that this work won the CMU SCS Alumni Award for Undergraduate Excellence, and 2nd place in the Math Competition at CMU’s Meeting of the Minds.
Parallel Functional Arrays. Ananya Kumar, Guy E. Blelloch and Robert Harper. Principles of Programming Languages (POPL) 2017. 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. If A is a functional array [0, 1, 2], then update(A, index=1, value=7) returns [0, 7, 2] but does not modify A. We allow operations on “old” arrays to be more expensive than on “new” arrays. Our main contributions are 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. We give a proof for our implementation and cost bounds.
Advised by Prof. Guy Blelloch and Prof. Bob Harper.
Making a Tree Bridge-Free by adding Minimal Edges (paper)
Our aim is to add the minimal number of edges to a given tree so that it is bridge-free. This is a solved problem, however we present a simpler construction, and show that our algorithm can generate all possible solutions. We also give novel near linear time algorithms for two special cases of the NP-complete weighted version of the problem. In our variants, the cost of adding an edge between two vertices is the sum of the weights of edges on the (unique) path between the two vertices. We prove an algorithm that makes the tree bridge free with minimal cost incurred, and an algorithm that adds the minimal number of edges to make the graph bridge-free, while maximizing the incurred cost.
Research I did in my senior year of high school with my classmate Ang Yan Sheng, advised by Prof. Tay Tiong Seng.