Eastern Great Lakes Theory Workshop Talk

Linear programming, robust satisfaction, and width-1 CSPs

Ryan O'Donnell, Carnegie Mellon University

Sunday, September 11, 9:00-10:00am

ABSTRACT

Say that an algorithm "robustly decides" a constraint satisfaction problem I if it distinguishes (1-epsilon)-satisfiable instances from (1-o_epsilon(1))-satisfiable instances. We will show that the canonical linear programming relaxation robustly decides I if and only if I is a "width-1" CSP.

Joint work with Gabor Kun, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou.

Speaker Bio

Ryan O'Donnell is an associate professor in the Computer Science Department at Carnegie Mellon University. He received a B. S. from the University of Toronto in 1999 and a Ph.D. from the MIT Mathematics Department in 2003. His Ph.D. advisor was Madhu Sudan. Following this he was a postdoc at IAS for a year in Avi Wigderson's group, and a postdoc at Microsoft Research for two years in Jennifer Chayes's group. He has been on the faculty of CMU since 2006, with a one-year visiting position at IAS. Ryan's research interests include Analysis of Boolean Functions, Hardness of Approximation, Learning Theory, and Probability.

< Schedule < EaGL-IV homepage