NP-hardness conjecture for Grothendieck d-norms

From papers

Let d,m,nNd,m,n\in\mathbb{N}. The real symmetric spaces Sn(R)\mathbb{S}^n(\mathbb{R}), real rectangular spaces Rm×n\mathbb{R}^{m\times n}, complex symmetric spaces Sn(C)\mathbb{S}^n(\mathbb{C}), and complex rectangular spaces Cm×n\mathbb{C}^{m\times n} be equipped with the corresponding Grothendieck dd-norms. NP-hardness conjecture. The following norms are all NP-hard:

  1. γ,dR\lVert\,\cdot\,\rVert_{\gamma,d}^{\mathbb{R}} and Γ,dR\lVert\,\cdot\,\rVert_{\Gamma,d}^{\mathbb{R}} on Sn(R)\mathbb{S}^n(\mathbb{R}) when d(d+1)/2nd(d+1)/2\le n;
  2. G,dR\lVert\,\cdot\,\rVert_{\mathsf{G},d}^{\mathbb{R}} on Rm×n\mathbb{R}^{m\times n} when d(d+1)/2m+nd(d+1)/2\le m+n;
  3. γ,dC\lVert\,\cdot\,\rVert_{\gamma,d}^{\mathbb{C}} and Γ,dC\lVert\,\cdot\,\rVert_{\Gamma,d}^{\mathbb{C}} on Sn(C)\mathbb{S}^n(\mathbb{C}) when d2nd^2\le n;
  4. G,dC\lVert\,\cdot\,\rVert_{\mathsf{G},d}^{\mathbb{C}} on Cm×n\mathbb{C}^{m\times n} when d2m+nd^2\le m+n.

The preceding discussion establishes NP-hardness over R\mathbb{R} for d=1d=1; the conjecture predicts NP-hardness throughout the dimension ranges not covered by the preceding stability proposition.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Shmuel Friedland and Lek-Heng Lim, “Symmetric Grothendieck inequality”, arXiv:2003.07345 (2020).

Solutions 0

No solutions have been posted yet.