Approximate Constraint Satisfaction Requires Large LP Relaxations

Speaker: Siu On Chan , Microsoft Research New England

Date: Wednesday, October 16, 2013

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host:

Contact: Ilya Razenshteyn, ilyaraz@csail.mit.edu

Relevant URL: http://www.ilyaraz.org/acseminar/

Speaker URL: None

Speaker Photo:
None

Reminders to: compalgsem@lists.csail.mit.edu, theory-seminars@lists.csail.mit.edu

Reminder Subject: TALK: Approximate Constraint Satisfaction Requires Large LP Relaxations

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy.

In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1/2 and any such linear program for Max 3-Sat has an integrality gap of 7/8.

Joint work with James Lee, Prasad Raghavendra, and David Steurer.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Ilya Razenshteyn at Monday, October 14, 2013 at 9:47 PM.