Education

In this work, we study the complexity of approximate hypergraph coloring, for both the maximization (finding a 2-coloring with fewest miscolored edges) and minimization (finding a proper coloring using fewest number of colors) versions, when the input hypergraph is promised to have properties related to discrepancy, strong colorability and rainbow colorability.

Senior thesis with Sariel Har-Peled in relation to Voronoi diagrams and separators. Provided approximation algorithms for inserting a minimal set of points in order to separate a partition of points in the Voronoi diagram. We also present a simple local search algorithm that is a PTAS for geometric hitting set of fat objects (which can also be used to approximate the optimal Voronoi partition).

Developed a near linear time FPTAS based on Har-Peled and Raichel's net and prune framework for the problem of finding the minimal ball enclosing k geometric objects from a set of n objects.

Proved that for any unary grammar G, there is a polynomial function P and an exponential function E, such that any string s of length n generated by the grammar has either at most P(n) ambiguous parse trees or at least E(n) ambiguous parse trees. Writeup in progress. The result is of a similar flavor to Klaus Wich's gap theorem.