- Approximate Constraint Sati...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in October 2013
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:
Created by Ilya Razenshteyn at Monday, October 14, 2013 at 9:47 PM.