Seminars & Colloquia

Sanjeev Arora

Computer Science, Princeton University

"Semidefinite Programming and its applications to Approximation Algorithms"

Monday February 09, 2009 04:00 PM
Location: 3211, EB2 NCSU Centennial Campus
(Visitor parking instructions)

This talk is part of the Triangle Computer Science Distinguished Lecturer Series

 

Abstract:

Computing approximately optimal solutions is an attractive way to cope with NP-hard optimization problems. In the past decade or so, semidefinite programming or SDP (a form of convex optimization that generalizes linear programming) has emerged as a powerful tool for designing such algorithms, and the last few years have seen a profusion of results (worst-case algorithms, average case algorithms, impossibility results, etc).

This talk will be a survey of this area and these recent results. We will see that analysing semidefinite program draws upon ideas from a variety of other areas, and has also led to new results in mathematics. At the end we will touch upon work that greatly improves the running time of SDP-based algorithms, making them potentially quite practical.

The survey will be essentially self-contained.

Short Bio:

Sanjeev Arora is Professor of Computer Science at Princeton University and works in computational complexity theory, approximation algorithms for NP-hard problems, geometric algorithms, and probabilistic algorithms. He has received the ACM Doctoral Dissertation Award, the SIGACT-EATCS Goedel Prize, and the Packard Fellowship.

To access the video of this talk, click here.

Host: Kamesh Munagala, Computer Science, Duke U.

Media Files:
No media files available at this time

Video Presentation: Host is responsible for requesting video recording by filling out this Web form. For other technical issues, contact us at csc_help@ncsu.edu.


Back to Seminar Listings
Back to Colloquia Home Page