Quadratic Forms on Graphs
| COMPUTER SCIENCE/DISCRETE MATH SEMINAR, II | |
| Topic: | Quadratic Forms on Graphs |
| Speaker: | Konstantin Makarychev |
| Affiliation: | Princeton University |
| Date: | Tuesday, February 22 |
| Time/Room: | 10:30am - 12:30pm/S-101 |
We introduce a new graph parameter, called the rothendieck constant of a graph. This parameter is a generalization of the classical Grothendieck constant; and it is equal to an integrality gap of a certain SDP problem, which has various
algorithmic applications. Our results improve a recent result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settle a problem of Megretski and of Charikar and Wirth.
Noga Alon described the motivation of the problem and our results at the members seminar on Monday, Jan 31. In my talk, I will give proofs of these results.