I'm a Ph.D. student in Theory, fortunate to be advised by Venkatesan Guruswami and Gary Miller
B.Sc. Mathematics & Computer Science. (Honors and Highest Distinction)
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).
Senior thesis with Mahesh Viswanathan in relation to Parikh equivalence of unary stochastic grammars and stochastic languages. Proved that every unary stochastic grammar with polynomially bounded ambiguity generates a stochastic language.
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.