About Me

Education

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

Where Sariel Har-Peled and Mahesh Viswanathan patiently introduced me to research.

Ph.D. - Carnegie Mellon University (Fall 2014 - Spring 2019)

I was very fortunate to have been advised by Venkat Guruswami.

Postdoc - Princeton University / Institute for Advanced Study (Fall 2019 - Spring 2021)

I am again fortunate to be at the Princeton TCS group from September 2019 to August 2020 hosted by Mark Braverman, and a member of Avi Wigderson's group at IAS from september 2020 to August 2021. I will also be part of the Simons Collaboration on Algorithms and Geometry.

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