About Me

Education

Carnegie Mellon University (Fall 2014)

I'm a Ph.D. student in Theory, fortunate to be advised by Venkatesan Guruswami

University of Illinois at Urbana-Champaign (Fall 2011 - Spring 2014)

B.Sc. Mathematics & Computer Science.

Research Summary

  • Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. With Mrinalkanti Ghosh, Madhur Tulsiani, Venkatesan Guruswami and Euiwoong Lee. In Submission. (Arxiv)

  • Certifying Random Polynomials Over the Unit Sphere via Sum of Squares Hierarchy. With Venkatesan Guruswami and Euiwoong Lee. Merged with "Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere".

  • Approximate Hypergraph Coloring under Low-discrepancy and Related Promises. With Venkatesan Guruswami and Euiwoong Lee. Approx 2015. (PDF)

    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.

  • Separating a Voronoi Diagram via Local Search. With Sariel Har-Peled. SoCG 2016. (PDF)

    Undergrad 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).

  • Unary Equivalence of Stochastic Grammars of Polynomially bounded ambiguity, and Stochastic Languages. With Mahesh Viswanathan. Manuscript. (PDF)

    Undergrad 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.

  • Near linear FPTAS for minimal ball enclosing k geometric objects. With Sariel Har-Peled. Manuscript.

    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.

  • Exponential or polynomial ambiguity of strings in a unary CFG. With Mahesh Viswanathan. Manuscript.

    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.

Current Interests

  • Approximation
  • Laserre/Sum of Squares
  • Random Matrix theory
  • Spectral theory

Contact Me

  •    Office: GHC 9003
  •    vpb@cs.cmu.edu