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
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
Constraint Satisfaction Problems Solvable by Local Consistency Methods, Journal of the ACM, vol.61, issue.1, 2014. ,
DOI : 10.1142/S021819670900524X
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
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
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 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
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
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
Approximation resistance from pairwise-independent subgroups, Journal of the ACM, vol.63, issue.3 27, 2016. ,
DOI : 10.1145/2873054
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
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
Convex relaxations and integrality gaps Conic and Polynomial Optimization, ser. International Series in Operations Research & Management Science, Handbook on Semidefinite, pp.139-169, 2012. ,
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
Robust Satisfiability for CSPs, ACM Transactions on Computation Theory, vol.5, issue.4, 2013. ,
DOI : 10.1145/2540090
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
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
Approximation algorithms and semidefinite programming, 2012. ,
DOI : 10.1007/978-3-642-22015-9
From Weak to Strong LP Gaps for all CSPs, p.497, 1608. ,
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
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
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
Some optimal inapproximability results, Journal of the ACM, vol.48, issue.4, pp.798-859, 2001. ,
DOI : 10.1145/502090.502098
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Existence theorems for weakly symmetric operations, Algebra universalis, vol.59, issue.3-4, pp.463-489, 2008. ,
DOI : 10.1007/s00012-008-2122-9
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. ,
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
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
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
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
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/
Semidefinite Programming, SIAM Review, vol.38, issue.1, pp.49-95, 1996. ,
DOI : 10.1137/1038003
Approximation algorithms, 2013. ,
DOI : 10.1007/978-3-662-04565-7
The design of approximation algorithms, 2011. ,
DOI : 10.1017/CBO9780511921735
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