Bhattiprolu, Vijay ;
Lee, Euiwoong ;
Tulsiani, Madhur
Separating the NPHardness of the Grothendieck Problem from the LittleGrothendieck Problem
Abstract
Grothendieck’s inequality [Grothendieck, 1953] states that there is an absolute constant K > 1 such that for any n× n matrix A,
‖A‖_{∞→1} := max_{s,t ∈ {± 1}ⁿ}∑_{i,j} A[i,j]⋅s(i)⋅t(j) ≥ 1/K ⋅ max_{u_i,v_j ∈ S^{n1}}∑_{i,j} A[i,j]⋅⟨u_i,v_j⟩.
In addition to having a tremendous impact on Banach space theory, this inequality has found applications in several unrelated fields like quantum information, regularity partitioning, communication complexity, etc. Let K_G (known as Grothendieck’s constant) denote the smallest constant K above. Grothendieck’s inequality implies that a natural semidefinite programming relaxation obtains a constant factor approximation to ‖A‖_{∞ → 1}. The exact value of K_G is yet unknown with the best lower bound (1.67…) being due to Reeds and the best upper bound (1.78…) being due to Braverman, Makarychev, Makarychev and Naor [Braverman et al., 2013]. In contrast, the little Grothendieck inequality states that under the assumption that A is PSD the constant K above can be improved to π/2 and moreover this is tight.
The inapproximability of ‖A‖_{∞ → 1} has been studied in several papers culminating in a tight UGCbased hardness result due to Raghavendra and Steurer (remarkably they achieve this without knowing the value of K_G). Briet, Regev and Saket [Briët et al., 2015] proved tight NPhardness of approximating the little Grothendieck problem within π/2, based on a framework by Guruswami, Raghavendra, Saket and Wu [Guruswami et al., 2016] for bypassing UGC for geometric problems. This also remained the best known NPhardness for the general Grothendieck problem due to the nature of the Guruswami et al. framework, which utilized a projection operator onto the degree1 Fourier coefficients of long code encodings, which naturally yielded a PSD matrix A.
We show how to extend the above framework to go beyond the degree1 Fourier coefficients, using the global structure of optimal solutions to the Grothendieck problem. As a result, we obtain a separation between the NPhardness results for the two problems, obtaining an inapproximability result for the Grothendieck problem, of a factor π/2 + ε₀ for a fixed constant ε₀ > 0.
BibTeX  Entry
@InProceedings{bhattiprolu_et_al:LIPIcs.ITCS.2022.22,
author = {Bhattiprolu, Vijay and Lee, Euiwoong and Tulsiani, Madhur},
title = {{Separating the NPHardness of the Grothendieck Problem from the LittleGrothendieck Problem}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {22:122:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15618},
URN = {urn:nbn:de:0030drops156186},
doi = {10.4230/LIPIcs.ITCS.2022.22},
annote = {Keywords: Grothendieck’s Inequality, Hardness of Approximation, Semidefinite Programming, Optimization}
}
25.01.2022
Keywords: 

Grothendieck’s Inequality, Hardness of Approximation, Semidefinite Programming, Optimization 
Seminar: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Issue date: 

2022 
Date of publication: 

25.01.2022 