The Grothendieck Constant of an Expander

COMPUTER SCIENCE/DISCRETE MATH II
Topic:	The Grothendieck Constant of an Expander
Speaker:	Noga Alon
Affiliation:	Tel Aviv University and IAS
Date:	Tuesday, March 28
Time/Room:	10:30am - 12:30pm/S-101

---

The Grothendieck constant of a graph is an invariant whose study, which is motivated by algorithmic applications, leads to several extensions of a classical inequality of Grothendieck. This invariant was introduced in a joint paper with Makarychev, Makarychev and Naor, in which we suggested a conjecture that determines its value (up to absolute constant factors) for every graph.

I will discuss the conjecture and its background, and will describe a recent joint result with Berger, showing that the conjecture holds for regular graphs with a large spectral gap.