14 citations · 20 across the 7 of their papers we have counts for
9 papers
PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren
We give simple deterministic reductions demonstrating the NP-hardness of approximating the nearest codeword problem and minimum distance problem within arbitrary constant factors (…
Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee +1
Finding sparse vectors is a fundamental problem that arises in several contexts including codes, subspaces, and lattices. In this work, we prove strong inapproximability results fo…
A PTAS for -Low Rank Approximation
Frank Ban, Vijay Bhattiprolu, Karl Bringmann +3
A number of recent works have studied algorithms for entrywise -low rank approximation, namely, algorithms which given an matrix (with ), output…
Approximating Operator Norms via Generalized Krivine Rounding
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2
We consider the -Grothendieck problem, which seeks to maximize the bilinear form for an input matrix over vectors with . The…
Inapproximability of Matrix Norms
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2
We study the problem of computing the norm of a matrix , defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac…
Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2
We consider the following basic problem: given an -variate degree- homogeneous polynomial with real coefficients, compute a unit vector that maximize…