V. Bhattiprolu

activity

20142025

most citedSum-of-Squares Certificates for Maxima of Random Tensors on the Sphere

14 citations · 20 across the 7 of their papers we have counts for

collaborators

Showing 2018Show all

3 papers · 1 filter

cs.DS2018

A PTAS for $ℓ_{p}$ -Low Rank Approximation

Frank Ban, Vijay Bhattiprolu, Karl Bringmann +3

A number of recent works have studied algorithms for entrywise $ℓ_{p}$ -low rank approximation, namely, algorithms which given an $n \times d$ matrix $A$ (with $n \geq d$ ), output…

cs.DS2018★ 2 cited

Approximating Operator Norms via Generalized Krivine Rounding

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2

We consider the $(ℓ_{p}, ℓ_{r})$ -Grothendieck problem, which seeks to maximize the bilinear form $y^{T} A x$ for an input matrix $A$ over vectors $x, y$ with $∥ x ∥_{p} = ∥ y ∥_{r} = 1$ . The…

cs.CC2018★ 2 cited

Inapproximability of Matrix $p \to q$ Norms

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2

We study the problem of computing the $p \to q$ norm of a matrix $A \in R^{m \times n}$ , defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac…

A PTAS for ℓp​-Low Rank Approximation

Approximating Operator Norms via Generalized Krivine Rounding

Inapproximability of Matrix p→q Norms

A PTAS for $ℓ_{p}$ -Low Rank Approximation

Inapproximability of Matrix $p \to q$ Norms