Speaker: Adam Sheffer, TAU
Title: Approximations via Semidefinite Programming: An Introduction

Abstract:
Semidefinite programming (or SDP) is a subfield of convex optimization,
which arose as a generalization of linear programming with many novel
applications. One such "recent" application is a powerful framework for
approximation algorithms. Currently, SDP-based algorithms obtain the best
approximation ratios for many major problems, such as graph coloring,
maximum cut, and Max-SAT.

In this talk, we try to provide a simple introduction to SDP-based
approximation algorithms, which seem to be a useful tool for theoretical
computer scientists. We will go over some theoretical background required
for the technique, present the technique by using some examples from the
founding paper [Goemans and Williamson `95], and discuss the analysis in
[Karger, Motwani, and Sudan `98] which has a more geometric flavor. No
recent results will be surveyed, and the talk will probably be too basic
for people who are already familiar with the subject.