V. Bhattiprolu

collaborators

Showing cs.DSShow 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

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.DS2015

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises

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

A hypergraph is said to be $χ$ -colorable if its vertices can be colored with $χ$ colors so that no hyperedge is monochromatic. $2$ -colorability is a fundamental property (called Pr…

A PTAS for ℓp​-Low Rank Approximation

Approximating Operator Norms via Generalized Krivine Rounding

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises

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