About Me

Education

Postdoc - Princeton University / Institute for Advanced Study (September 2019 - August 2021)

I am a postdoc 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 am also part of the Simons Collaboration on Algorithms and Geometry.

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

I was very fortunate to be advised by Venkat Guruswami.

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

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

Current Interests

  • Approximation / Hardness of Approximation
  • Sum of Squares / Polynomial Optimization
  • Operator Norms / Injective Tensor Norms
  • Functional Analysis
  • Spectral 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:
  •    vspvijay@math.ias.edu