Publications

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⟩

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⟩

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⟩

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⟩

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⟩

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⟩

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. ⟨10.1109/LICS.2017.8005087⟩. ⟨hal-01796715⟩

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. pp.17-27. ⟨hal-01762279⟩

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. ⟨hal-01730648⟩

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. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. ⟨hal-00830467⟩