About Me

Assistant Professor - University of Waterloo

Department of Combinatorics & Optimization

Teaching

Spring 2024, CO759: Approximation Algorithms and Inapproximability
Spring 2024, CO250: Introduction to Optimization
Spring 2023, CO250: Introduction to Optimization
Winter 2023, CO370: Deterministic OR Models

Advisees

Yang Xiao (Ph.D., Coadvised with Chaitanya Swamy)
Jacob Skitsko (Ph.D., Coadvised with Kostya Pashkovich)
Martin Liu (Masters)

Education

Postdoc - Princeton University / Institute for Advanced Study (September 2019 - July 2022)

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
  • Polynomial Maximization over Convex Sets
  • Functional Analysis
  • Asymptotic Convex Geometry
  • Spectral theory
  • Sum of Squares

Research Publications

  • Inapproximability of Sparsest Vector in a Real Subspace (Arxiv)

    With Euiwoong Lee
    In Submission.

  • Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem (PDF)

    With Euiwoong Lee and Madhur Tulsiani
    ITCS 2022

  • A Framework for Quadratic Form Maximization over Convex Sets through Non-Convex Relaxations (Full Version PDF)

    With Assaf Naor and Euiwoong Lee
    STOC 2021
    Invited Talks: Presented at SIAM AG'21 Conference on Applied Algebraic Geometry; Rutgers/Dimacs Theory Seminar 2021; IAS CSDM Seminar 2021

  • Inapproximability of Matrix p->q Norms (Arxiv)

    With Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee and Madhur Tulsiani
    SICOMP 2021
    Part of this work was announced in SODA 2019 in a merged abstract with the below paper

  • Approximating Operator Norms via Generalized Krivine Rounding (Arxiv)

    With Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee and Madhur Tulsiani
    SODA 2019

  • A PTAS for lp-Low Rank Approximation (Arxiv)

    With Frank Ban, Karl Bringmann, Pavel Kolev, Euiwoong Lee and David Woodruff
    SODA 2019

  • Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere (Arxiv)

    With Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee and Madhur Tulsiani
    FOCS 2017
    Invited Talks: Presented at 2017 Simons Workshop on Hierarchies, Extended Formulations and Matrix Analytic Techniques; CMU Theory Seminar 2017

  • Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere (Arxiv)

    With Venkatesan Guruswami and Euiwoong Lee
    RANDOM 2017

  • Parikh's Theorem for Weighted and Probabilistic Context Free Grammars (PDF)

    With Spencer Gordon and Mahesh Viswanathan
    QEST 2017

  • Separating a Voronoi Diagram via Local Search (Arxiv)

    With Sariel Har-Peled
    SoCG 2016

  • Approximate Hypergraph Coloring under Low-discrepancy and Related Promises (Arxiv)

    With Venkatesan Guruswami and Euiwoong Lee
    APPROX 2015

Contact Me

  •    Office:
  •    vbhattip@uwaterloo.ca