2 citations · 8 across the 7 of their papers we have counts for
8 papers
Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems
Mrinalkanti Ghosh
This thesis explores algorithmic applications and limitations of convex relaxation hierarchies for approximating some discrete and continuous optimization problems. - We show a dic…
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones +2
The Sum-of-Squares (SoS) hierarchy is a semi-definite programming meta-algorithm that captures state-of-the-art polynomial time guarantees for many optimization problems such as Ma…
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…
From Weak to Strong LP Gaps for all CSPs
Mrinalkanti Ghosh, Madhur Tulsiani
We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP…
Ornstein Isomorphism and Algorithmic Randomness
Mrinalkanti Ghosh, Satyadev Nandakumar, Atanu Pal
In 1970, Donald Ornstein proved a landmark result in dynamical systems, viz., two Bernoulli systems with the same entropy are isomorphic except for a measure 0 set. Keane and Smoro…
Predictive Complexity and Generalized Entropy Rate of Stationary Ergodic Processes
Mrinalkanti Ghosh, Satyadev Nandakumar
In the online prediction framework, we use generalized entropy of to study the loss rate of predictors when outcomes are drawn according to stationary ergodic distributions over th…