S. Arora, S. Rao, and U. V. Vazirani, Expander flows, geometric embeddings and graph partitioning, Journal of the ACM, vol.56, issue.2, 2009.
DOI : 10.1145/1007352.1007355

URL : http://www.cs.princeton.edu/~arora/pubs/arvfull.pdf

A. Atserias, A. Bulatov, and A. Dawar, Affine systems of equations and counting infinitary logic, Theoretical Computer Science, vol.410, issue.18, pp.1666-1683, 2009.
DOI : 10.1016/j.tcs.2008.12.049

URL : http://www.cs.sfu.ca/~abulatov/papers/definability.ps

L. Barto and M. Kozik, Constraint Satisfaction Problems Solvable by Local Consistency Methods, Journal of the ACM, vol.61, issue.1, 2014.
DOI : 10.1142/S021819670900524X

L. Barto, M. Kozik, and T. Niven, The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell), SIAM Journal on Computing, vol.38, issue.5, pp.1782-1802, 2009.
DOI : 10.1137/070708093

E. Ben-sasson and A. Wigderson, Short proofs are narrow---resolution made simple, Journal of the ACM, vol.48, issue.2, pp.149-169, 2001.
DOI : 10.1145/375827.375835

URL : http://www.cs.huji.ac.il/~elli/papers/width-journal03.ps

M. Bodirsky, Constraint Satisfaction Problems with Infinite Templates, Complexity of Constraints, ser. Lecture Notes in Computer Science, vol.6, issue.1-2, pp.196-228, 2008.
DOI : 10.1111/j.1467-8640.1990.tb00130.x

A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a 3-element set, Journal of the ACM, vol.53, issue.1, pp.66-120, 2006.
DOI : 10.1145/1120582.1120584

A. Bulatov, A. Krokhin, and P. Jeavons, Classifying the Complexity of Constraints Using Finite Algebras, SIAM Journal on Computing, vol.34, issue.3, pp.720-742, 2005.
DOI : 10.1137/S0097539700376676

URL : http://www.dur.ac.uk/andrei.krokhin/papers/SIAMclassifying.pdf

A. A. Bulatov, Complexity of conservative constraint satisfaction problems, ACM Transactions on Computational Logic, vol.12, issue.4, p.24, 2011.
DOI : 10.1145/1970398.1970400

URL : http://www.cs.sfu.ca/~abulatov/papers/consfull.ps

S. O. Chan, Approximation resistance from pairwise-independent subgroups, Journal of the ACM, vol.63, issue.3 27, 2016.
DOI : 10.1145/2873054

S. O. Chan, J. R. Lee, P. Raghavendra, and D. Steurer, Approximate constraint satisfaction requires large LP relaxations, Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS'13, pp.350-359, 2013.
DOI : 10.1109/focs.2013.45

URL : http://arxiv.org/pdf/1309.0563.pdf

M. Charikar, K. Makarychev, and Y. Makarychev, Integrality gaps for Sherali-Adams relaxations, Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, STOC '09, pp.283-292, 2009.
DOI : 10.1145/1536414.1536455

URL : http://ttic.uchicago.edu/%7Eyury/papers/sa-final.pdf

E. Chlamtá? and M. Tulsiani, Convex relaxations and integrality gaps Conic and Polynomial Optimization, ser. International Series in Operations Research & Management Science, Handbook on Semidefinite, pp.139-169, 2012.

D. A. Cohen, M. C. Cooper, P. Creed, P. Jeavons, and S. ?ivný, An algebraic theory of complexity for discrete optimisation, SIAM Journal on Computing, vol.42, issue.5, pp.915-1939, 2013.
DOI : 10.1137/130906398

URL : http://arxiv.org/pdf/1207.6692

V. Dalmau and A. A. Krokhin, Robust Satisfiability for CSPs, ACM Transactions on Computation Theory, vol.5, issue.4, 2013.
DOI : 10.1145/2540090

A. Dawar and P. Wang, Definability of semidefinite programming and lasserre lower bounds for CSPs, 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
DOI : 10.1109/LICS.2017.8005108

T. Feder and M. Y. Vardi, The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory, SIAM Journal on Computing, vol.28, issue.1, pp.57-104, 1998.
DOI : 10.1137/S0097539794266766

URL : http://theory.stanford.edu/~tomas/constraint.ps

B. Gärtner and J. Matou?ek, Approximation algorithms and semidefinite programming, 2012.
DOI : 10.1007/978-3-642-22015-9

M. K. Ghosh and M. Tulsiani, From Weak to Strong LP Gaps for all CSPs, p.497, 1608.

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, vol.42, issue.6, pp.1115-1145, 1995.
DOI : 10.1145/227683.227684

URL : http://www.almaden.ibm.com/cs/people/dpw/Cut/maxcut.ps

D. Grigoriev, Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity, Theoretical Computer Science, vol.259, issue.1-2, pp.613-622, 2001.
DOI : 10.1016/S0304-3975(00)00157-2

URL : https://doi.org/10.1016/s0304-3975(00)00157-2

V. Guruswami and Y. Zhou, Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set, Theory of Computing, vol.8, issue.1, pp.239-267, 2012.
DOI : 10.1137/1.9781611973082.122

URL : https://epubs.siam.org/doi/pdf/10.1137/1.9781611973082.122

J. Håstad, Some optimal inapproximability results, Journal of the ACM, vol.48, issue.4, pp.798-859, 2001.
DOI : 10.1145/502090.502098

P. Hell and J. Ne?et?il, On the complexity of H-coloring, Journal of Combinatorial Theory, Series B, vol.48, issue.1, pp.92-110, 1990.
DOI : 10.1016/0095-8956(90)90132-J

URL : https://doi.org/10.1016/0095-8956(90)90132-j

P. Jeavons, D. A. Cohen, and M. Gyssens, Closure properties of constraints, Journal of the ACM, vol.44, issue.4, pp.527-548, 1997.
DOI : 10.1145/263867.263489

URL : http://platon.cs.rhbnc.ac.uk/research/constraints/publications/pubs-ps/closure.ps

D. R. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM, vol.45, issue.2, pp.246-265, 1998.
DOI : 10.1145/274787.274791

URL : http://arxiv.org/pdf/cs/9812008

V. Kolmogorov, A. A. Krokhin, and M. Rolínek, The complexity of general-valued CSPs, Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS'15, pp.1246-1258, 2015.
DOI : 10.1109/focs.2015.80

V. Kolmogorov, J. Thapper, and S. ?ivný, The Power of Linear Programming for General-Valued CSPs, SIAM Journal on Computing, vol.44, issue.1, pp.1-36, 2015.
DOI : 10.1137/130945648

URL : https://hal.archives-ouvertes.fr/hal-01762346

P. K. Kothari, R. Meka, and P. Raghavendra, Approximating rectangles by Juntas and weakly-exponential lower bounds for LP relaxations of CSPs, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2017, 1610.
DOI : 10.1137/080733644

URL : http://arxiv.org/pdf/1610.02704

M. Kozik, A. Krokhin, M. Valeriote, and R. Willard, Characterizations of several Maltsev conditions, Algebra universalis, vol.64, issue.77, pp.205-224, 2015.
DOI : 10.1007/s00012-010-0082-3

URL : http://www.math.uwaterloo.ca/~rdwillar/documents/Publications/MaltsevPaper.pdf

M. Kozik and J. Ochremiak, Algebraic Properties of Valued Constraint Satisfaction Problem, Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP'15), pp.846-858, 2015.
DOI : 10.1007/978-3-662-47672-7_69

URL : http://arxiv.org/pdf/1403.0476

G. Kun, R. O. Donnell, S. Tamaki, Y. Yoshida, and Y. Zhou, Linear programming, width-1 CSPs, and robust satisfaction, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference on, ITCS '12, pp.484-495, 2012.
DOI : 10.1145/2090236.2090274

URL : http://www.cs.cmu.edu/%7Eodonnell/papers/width1.pdf

B. Larose and L. Zádori, Bounded width problems and algebras, Algebra universalis, vol.56, issue.3-4, pp.439-466, 2007.
DOI : 10.1007/s00012-007-2012-6

URL : http://www.mathstat.concordia.ca/faculty/larose/bounded_width_rev.pdf

J. B. Lasserre, An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs, Proceedings of the 8th Integer Programming and Combinatorial Optimization (IPCO'01), pp.293-303, 2001.
DOI : 10.1007/3-540-45535-3_23

M. Laurent, A Comparison of the Sherali-Adams, Lov??sz-Schrijver, and Lasserre Relaxations for 0???1 Programming, Mathematics of Operations Research, vol.28, issue.3, pp.470-496, 2003.
DOI : 10.1287/moor.28.3.470.16391

URL : https://ir.cwi.nl/pub/11670/11670B.pdf

J. R. Lee, P. Raghavendra, and D. Steurer, Lower Bounds on the Size of Semidefinite Programming Relaxations, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '15, 1411.
DOI : 10.1016/0022-0000(91)90024-Y

URL : http://arxiv.org/pdf/1411.6317

L. Lovász and A. Schrijver, Cones of Matrices and Set-Functions and 0???1 Optimization, SIAM Journal on Optimization, vol.1, issue.2, pp.166-190, 1991.
DOI : 10.1137/0801013

M. Maróti and R. Mckenzie, Existence theorems for weakly symmetric operations, Algebra universalis, vol.59, issue.3-4, pp.463-489, 2008.
DOI : 10.1007/s00012-008-2122-9

R. O. Donnell and Y. Zhou, Approximability and proof complexity, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13). Society for Industrial and Applied Mathematics, pp.1537-1556, 2013.

T. J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, pp.216-226, 1978.
DOI : 10.1145/800133.804350

G. Schoenebeck, Linear Level Lasserre Lower Bounds for Certain k-CSPs, 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp.593-602, 2008.
DOI : 10.1109/FOCS.2008.74

URL : http://web.eecs.umich.edu/~schoeneb/papers/Lasserre.pdf

H. D. Sherali and W. P. Adams, A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems, SIAM Journal on Discrete Mathematics, vol.3, issue.3, pp.411-430, 1990.
DOI : 10.1137/0403036

J. Thapper and S. ?ivný, The Power of Sherali--Adams Relaxations for General-Valued CSPs, SIAM Journal on Computing, vol.46, issue.4
DOI : 10.1137/16M1079245

URL : https://hal.archives-ouvertes.fr/hal-01796721

M. Tulsiani, CSP gaps and reductions in the lasserre hierarchy, Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, STOC '09, pp.303-312, 2009.
DOI : 10.1145/1536414.1536457

URL : http://eccc.hpi-web.de/report/2008/104/download/

L. Vandenberghe and S. P. Boyd, Semidefinite Programming, SIAM Review, vol.38, issue.1, pp.49-95, 1996.
DOI : 10.1137/1038003

V. V. Vazirani, Approximation algorithms, 2013.
DOI : 10.1007/978-3-662-04565-7

D. P. Williamson and D. B. Shmoys, The design of approximation algorithms, 2011.
DOI : 10.1017/CBO9780511921735

M. Yannakakis, Expressing combinatorial optimization problems by Linear Programs, Journal of Computer and System Sciences, vol.43, issue.3, pp.441-466, 1991.
DOI : 10.1016/0022-0000(91)90024-Y