3:30 pm, Lecture Hall 801
Goutham Rajendran
University of Chicago.
19-03-18

---

Abstract

About the Speaker:

Goutham was a undergraduate student at CMI and he is currently doing his Phd in Computer Science from University of Chicago. He is will be visiting us on Monday (19th March). He will be giving a special lecture at 3:30pm on SDP and LP hierarchies. He will also talk briefly about his recent results on this topic.

A brief description on what he plans to talk about:

We'll cover basic semidefinite programming and the Goemans Williamson algorithm which perhaps seriously started the study of SDPs for approximation. Then, we'll cover the Sherali-Adams hierarchy and the Lasserre hierarchy through applications; and mention Guruswamy and Sinop's result on how to use the hierarchies to solve a variety of problems on graphs which look like expanders(the so called low-threshold rank graphs). Time permitting, we will cover either the pseudodistribution view of the hierarchies, which give more insight on how the hierarchies work and how to fool them; or the Unique Games conjecture and Prasad Raghavendra's beautiful result on why it proves that SDPs are, in some sense, the most optimal algorithms for a huge class of problems and hence, we need not look further than SDPs.