Speaker: |
Suhail Sherif |

Organiser: |
Anand Deo |

Date: |
Friday, 8 Nov 2019, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

Suppose you are interested in calculating, for a given real matrix A, the maximum of sum A_ij d_i e_j, with the constraint that each d_i and e_j should be a real number between 1 and -1. (People interested in finding the largest cut in a weighted bipartite graph need not suppose.) 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.

This constant, 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 improved these bounds, to being at least ~1.676 and at most ~1.782.

We will see a proof of the ~1.782 upper bound, by Krivine in 1977. It is remarkably neat and elementary.