Publications

Johan Thapper, Stanislav Živný. The Limits of SDP Relaxations for General-Valued CSPs. ACM Transactions on Computation Theory, ACM, 2018, 10 (3), pp.1 - 22. 〈10.1145/3201777〉. 〈hal-01798805〉

Marek Karpinski, Narayanan Narayanan, Johan Thapper, Abdelhakim El Maftouhi, Laurent Rosaz, et al.. Tropical dominating sets in vertex-coloured graphs. Journal of Discrete Algorithms, Elsevier, 2018. 〈hal-01762194〉

Peter Jonsson, Johan Thapper. Tractability conditions for numeric CSPs. Theoretical Computer Science, Elsevier, 2018, 715, pp.21 - 34. 〈10.1016/j.tcs.2018.01.013〉. 〈hal-01796723〉

Johan Thapper, Stanislav Živný. The Power of Sherali--Adams Relaxations for General-Valued CSPs. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2017, 46 (4), pp.1241 - 1279. 〈10.1137/16M1079245〉. 〈hal-01796721〉

Johan Thapper, Stanislav Živný. The Complexity of Finite-Valued CSPs. Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63 (4), pp.1 - 33. 〈10.1145/2974019〉. 〈hal-01796719〉

Peter Jonsson, Johan Thapper. Constraint Satisfaction and Semilinear Expansions of Addition over the Rationals and the Reals. Journal of Computer and System Sciences, Elsevier, 2016, 82 (5), pp.912 - 928. 〈10.1016/j.jcss.2016.03.002〉. 〈hal-01796722〉

Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper. An approximability-related parameter on graphs―-properties and applications. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.33--66. 〈hal-01196862〉

Vladimir Kolmogorov, Johan Thapper, Stanislav Živný. The Power of Linear Programming for General-Valued CSPs. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2015, 44 (1), pp.1 - 36. 〈10.1137/130945648〉. 〈hal-01762346〉

Johan Thapper, Stanislav Zivny. Necessary Conditions for Tractability of Valued CSPs. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (4), pp.2361 - 2384. 〈10.1137/140990346〉. 〈hal-01762342〉

Manuel Bodirsky, Dugald Macpherson, Johan Thapper. Constraint Satisfaction Tractability from Semi-lattice Operations on Infinite Sets. ACM Transactions on Computational Logic, Association for Computing Machinery, 2013, 14 (4), pp.30:1-19. 〈10.1145/2528933〉. 〈hal-00756929〉

Johan Thapper, Stanislav Zivny. The limits of SDP relaxations for general-valued CSPs. 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jun 2017, Reykjavik, Iceland. IEEE, 〈10.1109/LICS.2017.8005087〉. 〈hal-01796715〉

Johan Thapper. Cohérences et dichotomies parmi des CSP pondérés. JFPC 2016 : Actes des Douzièmes Journées Francophones de Programmation par Contraintes, Jun 2016, Montpellier, France. pp.16-17, 2016. 〈hal-01730648〉

Laurent Rosaz, Marek Karpinski, Narayanan Narayanan, Johan Thapper, Abdelhakim El Maftouhi, et al.. Tropical Dominating Sets in Vertex-Coloured Graphs. 10th International Workshop on Algorithms and Computation (WALCOM 2016), 2016, Katmandu, Nepal. 9627, pp.17-27, 2016, LNCS. 〈hal-01762279〉

Johan Thapper, Stanislav Zivny. Sherali-Adams relaxations for valued CSPs. 42nd International Colloquium on Automata, Languages, and Programming (ICALP-2015), 2015, Kyoto, Japan. 〈hal-01762339〉

Peter Jonsson, Johan Thapper. Affine consistency and the complexity of semilinear constraints. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014), 2014, Budapest, Hungary. 〈hal-01762331〉

Johan Thapper. The Complexity of Valued Constraint Satisfaction Problems in a Nutshell. Simon de Givry. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes. 〈hal-00830467〉