Professor David Cohen

  1. Article › Research › Peer-reviewed
  2. Published

    Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search

    Kaznatcheev, A., Cohen, D. & Jeavons, P., 29 Nov 2020, In: Journal of Artificial Intelligence Research. 69, p. 1077-1102 26 p., 12156.

    Research output: Contribution to journalArticlepeer-review

  3. Published

    Steepest ascent can be exponential in bounded treewidth problems

    Cohen, D. A., Cooper, M. C., Kaznatcheev, A. & Wallace, M., May 2020, In: Operations Research Letters. 48, 3, p. 217-224 8 p.

    Research output: Contribution to journalArticlepeer-review

  4. Published

    Supermodular functions and the complexity of MAX CSP

    Cohen, D., Cooper, M., Jeavons, P. & Krokhin, A., 2005, In: Discrete Applied Mathematics. 149, p. 53-72 20 p.

    Research output: Contribution to journalArticlepeer-review

  5. Published

    Symmetry definitions for constraint satisfaction problems

    Cohen, D., Jeavons, P., Jefferson, C., Petrie, K. & Smith, B., 2006, In: Constraints. 11, p. 115-137 23 p.

    Research output: Contribution to journalArticlepeer-review

  6. Published

    The complexity of soft constraint satisfaction

    Cohen, D., Cooper, M., Jeavons, P. & Krokhin, A., 2006, In: Artificial Intelligence. 170, p. 983-1016 34 p.

    Research output: Contribution to journalArticlepeer-review

  7. Published

    The expressive power of binary submodular functions

    Zivný, S., Cohen, D. A. & Jeavons, P. G., 2009, In: Discrete Applied Mathematics. 157, 15, p. 3347-3358 12 p.

    Research output: Contribution to journalArticlepeer-review

  8. Published

    The expressive power of valued constraints: Hierarchies and collapses

    Cohen, D. A., Jeavons, P. G. & Živný, S., 6 Dec 2008, In: Theoretical Computer Science. 409, 1, p. 137-153 17 p.

    Research output: Contribution to journalArticlepeer-review

  9. Published

    The power of propagation: when GAC is enough

    Cohen, D. & Jeavons, P., Jan 2017, In: Constraints. 22, p. 3-23 21 p.

    Research output: Contribution to journalArticlepeer-review

  10. Published

    The tractability of CSP classes defined by forbidden patterns

    Cohen, D. A., Cooper, M. C., Creed, P., Marx, D. & Salamon, A. Z., Sep 2012, In: Journal of Artificial Intelligence Research. 45, p. 47-78 3651.

    Research output: Contribution to journalArticlepeer-review

  11. Published

    Tractable Decision for a Constraint Language Implies Tractable Search

    Cohen, D. A., 2004, In: Constraints. 9, 3, p. 219-229 11 p.

    Research output: Contribution to journalArticlepeer-review

  12. Published

    Variable and value elimination in binary constraint satisfaction via forbidden patterns

    Cohen, D., Cooper, M., Escamocher, G. & Zivny, S., Nov 2015, In: Journal of Computer and System Sciences. 81, 7, p. 1127–1143 17 p.

    Research output: Contribution to journalArticlepeer-review

  13. Chapter › Research
  14. Published

    A Structural Decomposition for Hypergraphs

    Jeavons, P. G., Cohen, D. A. & Gyssens, M., 1994, Jerusalem Combinatorics ’93. Barcelo, H. & Kalai, G. (eds.). American Mathematical Society, p. 161-177 17 p. (Contemporary Mathematics; vol. 178).

    Research output: Chapter in Book/Report/Conference proceedingChapter

  15. Published

    Parameterized Complexity of the Workflow Satisfiability Problem

    Cohen, D., Crampton, J., Gutin, Z. & Wahlstrom, M., 2017, Combinatorial Optimization and Graph Algorithms. Fukunaga, T. & Kawarabayashi, K. (eds.). Springer-Verlag, p. 101-120 20 p.

    Research output: Chapter in Book/Report/Conference proceedingChapter

  16. Published

    The complexity of constraint languages

    Cohen, D. & Jeavons, P., 2006, Handbook of Constraint Programming. Rossi, F., van Beek, P. & Walsh, T. (eds.). Elsevier

    Research output: Chapter in Book/Report/Conference proceedingChapter

  17. Published

    The Expressive Power of Valued Constraints: Hierarchies and Collapses

    Cohen, D., Jeavons, P. & ŽZivný, S., 2007, Principles and Practice of Constraint Programming – CP 2007. Bessière, C. (ed.). Berlin and Heidelberg: Springer, p. 798-805 8 p.

    Research output: Chapter in Book/Report/Conference proceedingChapter

  18. Conference contribution › Research
  19. Published

    A Substitution Operation for Constraints

    Jeavons, P. G., Cohen, D. A. & Cooper, M. C., 1 May 1994, Principles and Practice of Constraint Programming: Second International Workshop, PPCP '94 Rosario, Orcas Island, WA, USA, May 2–4, 1994 Proceedings. Borning, A. (ed.). Vol. 874. p. 1-9

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  20. Published

    An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection

    Cohen, D. A., Creed, P., Jeavons, P. G. & Živný, S., 2011, Mathematical Foundations of Computer Science 2011: 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011: Proceedings. Springer, p. 231-242 (Lecture Notes in Computer Science; vol. 6907).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  21. Published

    Engineering Algorithms for Workflow Satisfiability Problem with User-Independent Constraints

    Cohen, D., Crampton, J., Gagarin, A., Gutin, G. & Jones, M., 2014, FAW 2014. (Lecture Notes in Computer Science; vol. 8497).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  22. Published

    On Singleton Arc Consistency for CSPs Defined by Monotone Patterns

    Carbonnel, C., Cohen, D. A., Cooper, M. C. & Živný, S., 20 Feb 2018, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018. Niedermeier, R. & Vallée, B. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 96. p. 19:1-19:15 15 p. 19

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  23. Published

    The Expressive Power of Binary Submodular Functions

    Zivný, S., Cohen, D. A. & Jeavons, P. G., 2009, MFCS 2009. p. 744-757

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  24. Paper › Research › Not peer-reviewed
  25. Published

    A complete characterization of complexity for Boolean constraint optimization problems

    Cohen, D., Cooper, M. & Jeavons, P., 2004, p. 212-226.

    Research output: Contribution to conferencePaper

  26. Published

    A New Classs of Binary CSPs for which Arc-Constistency Is a Decision Procedure

    Cohen, D. A., 2003, p. 807-811.

    Research output: Contribution to conferencePaper

  27. Published

    A Test for Tractability

    Jeavons, P. G., Cohen, D. A. & Gyssens, M., 1996, p. 267-281.

    Research output: Contribution to conferencePaper

  28. Published

    A Unified Theory of Structural Tractability for Constraint Satisfaction and Spread Cut Decomposition.

    Cohen, D. A., Jeavons, P. & Gyssens, M., 2005, p. 72-77.

    Research output: Contribution to conferencePaper

  29. Published

    A Unifying Framework for Tractable Constraints

    Jeavons, P. G., Cohen, D. A. & Gyssens, M., 1995, p. 276-291.

    Research output: Contribution to conferencePaper