SCS Alumni Award for Undergraduate Excellence, and 2nd place in Math Competition at Meeting of the Minds 2017. Accepted to the Fall Workshop on Computational Geometry, and submitting a revised version to the Symposium on Computational Geometry (SoCG).
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 Prof. Avrim Blum and collaborated with Lin Yang, Harry Lang, Prof. Vladimir Braverman.
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 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.