Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LINEAR PROGRAMMING HIERARCHIES:
Reports tagged with linear programming hierarchies:
TR09-061 | 2nd July 2009
Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

Optimal Sherali-Adams Gaps from Pairwise Independence

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 ... more >>>




ISSN 1433-8092 | Imprint