SDP Integrality Gaps with Local L1-Embeddability

COMPUTER SCIENCE/DISCRETE MATH I
Topic:	SDP Integrality Gaps with Local L1-Embeddability
Speaker:	Subhash Khot
Affiliation:	Courant Institute, NYU
Date:	Monday, May 11
Time/Room:	11:15am - 12:15pm/S-101

---

I will present a construction of an n-point negative type metric such that every t-point sub-metric is isometrically L1-embeddable, but embedding the whole metric into L1 incurs distortion at least k, where both t and k are (\log\log\log n)^{\Omega(1)}. The result can also be interpreted as a construction of an integrality gap instace for SPARSEST CUT problem, for a combination of a basic SDP relaxation and t rounds of Sherali-Adams LP relaxation. Similar integrality gap holds for the MAXIMUM CUT problem.
Joint work with Rishi Saket.