About Me

Education

Carnegie Mellon University (Fall 2014 - May 2019 (expected))

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

I am currently on the Academic Job Market.

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

B.Sc. Mathematics & Computer Science.

Current Interests

  • Approximation
  • Sum of Squares
  • Optimization over the Sphere
  • Operator Norms
  • Functional Analysis
  • Spectral theory
  • Random Matrix theory

Research Summary

  • Approximating Opertor Norms via Generalized Krivine Rounding. With Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee and Madhur Tulsiani. SODA 2019 (merged acceptance with below). (Arxiv)

  • Inapproximability of Matrix p->q Norms. With Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee and Madhur Tulsiani. SODA 2019 (merged acceptance with above). (Arxiv)

  • A PTAS for lp-Low Rank Approximation. With Frank Ban, Karl Bringmann, Pavel Kolev, Euiwoong Lee and David Woodruff. SODA 2019. (Arxiv)

  • Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere. With Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee and Madhur Tulsiani. FOCS 2017. (Arxiv)

  • Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. With Venkatesan Guruswami and Euiwoong Lee. RANDOM 2017. (Arxiv)

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

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

  • Parikh's Theorem for Weighted and Probabilistic Context Free Grammars. With Spencer Gordon and Mahesh Viswanathan. QEST 2017. (PDF)

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

Contact Me

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