BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1011
DTSTAMP:20230914T125947Z
SUMMARY:Grothendieck's Inequality
DESCRIPTION:Speaker: Suhail Sherif\n\nAbstract: \nAbstract: The year was 19
53. Rajendra Prasad was still the president of India after winning the pre
sidential election one year prior. On the other side of the globe\, a jour
nal in São Paulo published a paper by Alexander Grothendieck. "Résumé d
e la théorie métrique des produits tensoriels topologiques\," or\, comme
nt dites-vous... "Summary of the metric theory of topological tensor produ
cts." The central theorem of this paper is now known as Grothendieck's ine
quality. For nearly 15 years\, nobody seemed to care about it. In 1968\, L
indenstrauss and Pełczyński published a paper highlighting\, reformulati
ng and building on the various gems in Grothendieck's paper. One of their
reformulations of Grothendieck's inequality is extremely relevant to compl
exity theory.\nSuppose you are interested in calculating\, for a given rea
l matrix A\, the maximum of sum A_ij d_i e_j\, with the constraint that ea
ch d_i and e_j should be a real number between 1 and -1. (People intereste
d in finding the largest cut in a weighted bipartite graph need not suppos
e.) Grothendieck's inequality says that you might as well maximise over d_
i and e_j being real vectors of arbitrary dimension\, but with the norm of
each vector being at most 1. You might get a larger maximum in the latter
case\, but it is larger by at most a multiplicative constant.\nThis const
ant\, maximised over all matrices A\, is known as Grothendieck's constant.
He showed it is at least ~1.5 and at most ~2.3. Subsequent works have imp
roved these bounds\, to being at least ~1.676 and at most ~1.782.\nWe will
see a proof of the ~1.782 upper bound\, by Krivine in 1977. It is remarka
bly neat and elementary.\n
URL:https://www.tcs.tifr.res.in/web/events/1011
DTSTART;TZID=Asia/Kolkata:20191108T171500
DTEND;TZID=Asia/Kolkata:20191108T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR