Tutte seminar - Costis GeorgiouExport this event to calendar

Friday, December 10, 2010 — 3:30 PM to 4:30 PM EST

SDP Integrality Gaps for Constraint Satisfaction Problems, from Pairwise Independence

Speaker: Levent Tunçel
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by P contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on n variables cannot be approximated better than the trivial (random) approximation, even after augmenting the natural semidefi nite relaxation with Omega(n) levels of the Sherali-Adams hierarchy. It was recently shown that under the Unique Game Conjecture, CSPs for predicates satisfying this condition cannot be approximated better than the trivial approximation. Our results can be viewed as an unconditional analogue of this result in a restricted computational model. We also introduce a new generalization of techniques to define consistent local distributions over partial assignments to variables in the problem, which is often the crux of proving lower bounds for such hierarchies. 


This is joint work with Siavosh Benabbas, Avner Magen and Madhur Tulsiani.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (141)
    1. October (12)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)