Vijay Bhattiprolu

According to our database, Vijay Bhattiprolu authored at least 17 papers between 2014 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Inapproximability of Sparsest Vector in a Real Subspace.

Vijay Bhattiprolu, Euiwoong Lee

Electron. Colloquium Comput. Complex., 2024

2023

Inapproximability of Matrix p → q Norms.

Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

SIAM J. Comput., February, 2023

2022

Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem.

Vijay Bhattiprolu, Euiwoong Lee, Madhur Tulsiani

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

A framework for quadratic form maximization over convex sets through nonconvex relaxations.

Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2019

Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness.

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A PTAS for ℓp-Low Rank Approximation.

Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Approximating Operator Norms via Generalized Krivine Rounding.

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2018

Inapproximability of Matrix p→q Norms.

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2018

A PTAS for 𝓁_p-Low Rank Approximation.

Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff

CoRR, 2018

2017

Extending Parikh's Theorem to Weighted and Probabilistic Context-Free Grammars.

Vijay Bhattiprolu, Spencer Gordon, Mahesh Viswanathan

Proceedings of the Quantitative Evaluation of Systems - 14th International Conference, 2017

Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere.

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere.

Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee

Proceedings of the Approximation, 2017

2016

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere.

Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2016

Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy.

Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee

CoRR, 2016

Separating a Voronoi Diagram via Local Search.

Vijay V. S. P. Bhattiprolu, Sariel Har-Peled

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises.

Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee

Proceedings of the Approximation, 2015

2014

Separating a Voronoi Diagram.

Vijay V. S. P. Bhattiprolu, Sariel Har-Peled

CoRR, 2014