Publications

A full list of my publications, grouped by research area. Where a conference paper was later extended to a journal version, both are listed under a single entry. A BibTeX file of all entries is also available, and you can find citation metrics on Google Scholar.

Permutation Group Computation

Christopher Jefferson, Markus Pfeiffer, Wilf A. Wilson, Rebecca Waldecker. Permutation Group Algorithms Based on Directed Graphs. Journal of Algebra 585, pp. 723–758, 2021. PDF

: New framework for permutation group problems (set stabilisers, intersections, conjugacy, isomorphisms) using labelled directed graphs instead of ordered partitions. Implemented in the GraphBacktracking package for GAP.

Christopher Jefferson, Rebecca Waldecker, Wilf A. Wilson. Perfect Refiners for Permutation Group Backtracking Algorithms. Journal of Symbolic Computation 114, pp. 18–36, 2023. PDF

: Introduces perfect refiners — refiners with maximal pruning power. Classifies which groups/cosets admit perfect refiners across different search formulations (partitions, ordered partitions, graphs). Implemented in Vole.

Christopher Jefferson, Rebecca Waldecker, Wilf A. Wilson. Computing Canonical Images in Permutation Groups with Graph Backtracking. Journal of Computational Algebra 8, 100010, 2023. PDF

: Applies graph backtracking techniques to compute canonical images of combinatorial objects under permutation group actions.

Mun See Chang, Christopher Jefferson. Disjoint Direct Product Decompositions of Permutation Groups. Journal of Symbolic Computation 108, pp. 1–16, 2022. PDF

: Polynomial time algorithm for computing the finest disjoint direct product decomposition of a permutation group given by generators.

Mun See Chang, Christopher Jefferson, Colva M. Roney-Dougal. Computing Normalisers of Intransitive Groups. Journal of Algebra 605, pp. 429–458, 2022. PDF

: Algorithms for computing normalisers of intransitive permutation groups in the symmetric group.

Christopher Jefferson, Markus Pfeiffer, Rebecca Waldecker. New Refiners for Permutation Group Search. Journal of Symbolic Computation 92, pp. 70–92, 2019. PDF

: New refiners for partition backtrack search in permutation groups, improving on the classical approach of Leon.

Christopher Jefferson, Eliza Jonauskyte, Markus Pfeiffer, Rebecca Waldecker. Minimal and Canonical Images. Journal of Algebra 521, pp. 481–506, 2019. PDF

: Theoretical foundations and algorithms for computing minimal and canonical images of combinatorial objects under group actions.

Paula Hähndel, Christopher Jefferson, Markus Pfeiffer, Rebecca Waldecker. Computational Aspects of Orbital Graphs. arXiv:1703.04272, 2017. PDF

: Introduces orbital graphs and classifies “futile” orbital graphs, showing how they improve search algorithms for permutation groups.

The Essence Language and Conjure

Özgür Akgün, Alan M. Frisch, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale. Conjure: Automatic Generation of Constraint Models from Problem Specifications. Artificial Intelligence 310, 103751, 2022. PDF

: Full journal treatment of the Conjure automated constraint modelling system. Users write abstract Essence specifications and Conjure automatically refines them into concrete constraint models. Earlier versions at AAAI 2011, CP 2013, ECAI 2014.

Özgür Akgün, Alan M. Frisch, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale, András Z. Salamon. Towards Reformulating Essence Specifications for Robustness. arXiv:2111.00821, 2021. PDF

: Recovering type and domain information to increase robustness of constraint models when users omit details in Essence specifications.

Peter Nightingale, Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, Patrick Spracklen. Automatically Improving Constraint Models in Savile Row. Artificial Intelligence 251, pp. 35–61, 2017. PDF

: Automatic model improvement techniques in Savile Row, including associative-commutative common subexpression elimination. Earlier version at CP 2014.

Ian P. Gent, Bilal Syed Hussain, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Glenna F. Nightingale, Peter Nightingale. Discriminating Instance Generation for Automated Constraint Model Selection. CP 2014, pp. 356–365. PDF

: Generates discriminating problem instances to distinguish between different constraint models, supporting automated model selection.

Özgur Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale. Breaking Conditional Symmetry in Automated Constraint Modelling with Conjure. ECAI 2014, pp. 3–8. PDF

: Handles conditional symmetries that arise during automated constraint modelling in Conjure.

Özgur Akgün, Alan M. Frisch, Ian P. Gent, Bilal Syed Hussain, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Peter Nightingale. Automated Symmetry Breaking and Model Selection in Conjure. CP 2013, pp. 107–116. PDF

: Automates both symmetry breaking and model selection within the Conjure constraint modelling pipeline.

Özgur Akgün, Ian Miguel, Christopher Jefferson, Alan M. Frisch, Brahim Hnich. Extensible Automated Constraint Modelling. AAAI 2011, 25(1), pp. 4–11. PDF

: Extends Conjure’s automated constraint modelling capabilities with an extensible architecture.

Andrea Rendl, Ian Miguel, Ian P. Gent, Christopher Jefferson. Automatically Enhancing Constraint Model Instances during Tailoring. SARA 2009. PDF

: Automatically improves constraint model instances during the tailoring phase.

Alan M. Frisch, Warwick Harvey, Christopher Jefferson, Bernadette Martínez-Hernández, Ian Miguel. Essence: A Constraint Language for Specifying Combinatorial Problems. Constraints 13(3), pp. 268–306, 2008. PDF

: Defines the Essence constraint specification language, supporting abstract decision variables with types such as set, multiset, function, and relation.

Alan M. Frisch, Matthew Grum, Christopher Jefferson, Bernadette Martínez-Hernández, Ian Miguel. The Design of Essence: A Constraint Language for Specifying Combinatorial Problems. IJCAI 2007, pp. 80–87. PDF

: Conference paper presenting the design principles behind Essence.

Alan M. Frisch, Christopher Jefferson, Bernadette Martínez-Hernández, Ian Miguel. The Rules of Constraint Modelling. IJCAI 2005, pp. 109–116. PDF

: Identifies and codifies rules that guide effective constraint modelling practice.

Constraint Propagation and Solving

Özgür Akgün, Ian P. Gent, Christopher Jefferson, Zeynep Kiziltan, Ian Miguel, Peter Nightingale, András Z. Salamon, Felix Ulrich-Oltean. TabID: Automatic Identification and Tabulation of Subproblems in Constraint Models. Journal of Artificial Intelligence Research 82, pp. 1999–2056, 2025. PDF

: Entirely automated method for identifying promising subproblems for tabulation in constraint programming. Earlier version at CP 2018.

Özgür Akgün, Jessica Enright, Christopher Jefferson, Ciaran McCreesh, Patrick Prosser, Steffen Zschaler. Finding Subgraphs with Side Constraints. CPAIOR 2021, pp. 348–364. PDF

: Extends subgraph finding problems with additional side constraints using constraint programming.

Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale. Metamorphic Testing of Constraint Solvers. CP 2018, pp. 727–736. PDF

: Applies metamorphic testing to constraint solvers, generating related test inputs to detect bugs without a test oracle.

Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale. Exploiting Short Supports for Improved Encoding of Arbitrary Constraints into SAT. CP 2016, pp. 3–12. PDF

: Uses short support structures to produce more compact SAT encodings of arbitrary constraints.

David A. Cohen, Christopher Jefferson, Karen E. Petrie. A Theoretical Framework for Constraint Propagator Triggering. SOCS 2016, 7(1), pp. 19–27. PDF

: Theoretical analysis of when and how constraint propagators should be triggered during search.

Ian P. Gent, Christopher Jefferson, Steve Linton, Ian Miguel, Peter Nightingale. Generating Custom Propagators for Arbitrary Constraints. Artificial Intelligence 211, pp. 1–33, 2014. PDF

: Automatically generates specialised constraint propagators from high-level constraint descriptions.

Thomas W. Kelsey, Lars Kotthoff, Christopher Jefferson, Stephen A. Linton, Ian Miguel, Peter Nightingale, Ian P. Gent. Qualitative Modelling via Constraint Programming. Constraints 19(2), pp. 163–173, 2014. PDF

Peter Nightingale, Ian P. Gent, Christopher Jefferson, Ian Miguel. Short and Long Supports for Constraint Propagation. Journal of Artificial Intelligence Research 46, pp. 1–45, 2013. PDF

: Identifies short supports as important for constraint propagation. Introduces HaggisGAC, an efficient general-purpose propagation algorithm faster than GAC-Schema by orders of magnitude.

Christopher Jefferson, Peter Jeavons, Martin J. Green, Marc R.C. van Dongen. Representing and Solving Finite-Domain Constraint Problems Using Systems of Polynomials. Annals of Mathematics and Artificial Intelligence 67(3), pp. 359–382, 2013. PDF

: Encodes finite-domain constraint problems as systems of polynomials.

Christopher Jefferson, Peter Nightingale. Extending Simple Tabular Reduction with Short Supports. IJCAI 2013, pp. 573–579. PDF

: Extends the STR algorithm to exploit short supports, improving table constraint propagation.

Dharini Balasubramaniam, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Peter Nightingale. An Automated Approach to Generating Efficient Constraint Solvers. ICSE 2012, pp. 661–671. PDF

: Software engineering approach to automatically assembling efficient constraint solvers from components.

Peter Nightingale, Ian P. Gent, Christopher Jefferson, Ian Miguel. Exploiting Short Supports for Generalised Arc Consistency for Arbitrary Constraints. IJCAI 2011, pp. 623–628. PDF

: Conference version introducing short supports for GAC. Extended to the JAIR 2013 journal paper.

Ian P. Gent, Christopher Jefferson, Lars Kotthoff, Ian Miguel. Modelling Constraint Solver Architecture Design as a Constraint Problem. arXiv:1110.6290, 2011. PDF

Dharini Balasubramaniam, Lakshitha de Silva, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Peter Nightingale. Dominion: An Architecture-Driven Approach to Generating Efficient Constraint Solvers. WICSA 2011, pp. 228–231. PDF

Christopher Jefferson, Neil C.A. Moore, Peter Nightingale, Karen E. Petrie. Implementing Logical Connectives in Constraint Programming. Artificial Intelligence 174(16–17), pp. 1407–1429, 2010. PDF

: How logical connectives (and, or, implication, etc.) should be implemented efficiently in constraint solvers.

Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale. Generating Special-Purpose Stateless Propagators for Arbitrary Constraints. CP 2010, pp. 206–220. PDF

: Precursor to the AI 2014 journal paper on custom propagators.

Ian P. Gent, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Neil C.A. Moore, Peter Nightingale, Karen E. Petrie. Learning When to Use Lazy Learning in Constraint Solving. ECAI 2010, pp. 873–878. PDF

Christopher Jefferson, Serdar Kadioglu, Karen E. Petrie, Meinolf Sellmann, Stanislav Živný. Same-Relation Constraints. CP 2009, pp. 470–485. PDF

Martin J. Green, Christopher Jefferson. Structural Tractability of Propagated Constraints. CP 2008, pp. 372–386. PDF

: Analyses when constraint propagation can be performed in polynomial time based on constraint network structure.

Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale. Data Structures for Generalised Arc Consistency for Extensional Constraints. AAAI 2007, pp. 191–197. PDF

: Efficient data structures for maintaining generalised arc consistency on table constraints.

Christopher Jefferson. Representations in Constraint Programming. PhD thesis, University of York, 2007. PDF

Ian P. Gent, Christopher Jefferson, Ian Miguel. Watched Literals for Constraint Propagation in Minion. CP 2006, pp. 182–197. PDF

: Adapts the watched literal scheme from SAT solvers to constraint propagation in Minion.

Ian P. Gent, Christopher Jefferson, Ian Miguel. Minion: A Fast Scalable Constraint Solver. ECAI 2006, pp. 98–102. PDF

: Introduces Minion, a constraint solver designed for speed and scalability using watched literals and cache-aware data structures.

Symmetry

Özgür Akgün, Mun See Chang, Ian P. Gent, Christopher Jefferson. Faster Symmetry Breaking Constraints for Abstract Structures. AAAI 2026, pp. 14132–14139. PDF

: Improves symmetry breaking constraints for unnamed types in abstract constraint specifications.

Özgür Akgün, Mun See Chang, Ian P. Gent, Christopher Jefferson. Breaking the Symmetries of Indistinguishable Objects. CPAIOR 2025, pp. 152–168. PDF

: Defines and breaks symmetries arising from indistinguishable objects in complex types. Provides complete symmetry breaking for unnamed types in Essence.

Christopher Jefferson, Karen E. Petrie. Automatic Generation of Constraints for Partial Symmetry Breaking. CP 2011, pp. 729–743. PDF

Andrew Grayland, Christopher Jefferson, Ian Miguel, Colva M. Roney-Dougal. Minimal Ordering Constraints for Some Families of Variable Symmetries. Annals of Mathematics and Artificial Intelligence 57(1), pp. 75–102, 2009. PDF

: Derives minimal sets of ordering constraints sufficient to break variable symmetries in several important families.

Karen E. Petrie, Christopher Jefferson. Efficiently Solving Problems Where the Solutions Form a Group. CP 2008, pp. 529–533. PDF

David Cohen, Peter Jeavons, Christopher Jefferson, Karen E. Petrie, Barbara M. Smith. Symmetry Definitions for Constraint Satisfaction Problems. Constraints 11(2–3), pp. 115–137, 2006. PDF

: Reviews and unifies the many definitions of symmetry for CSPs. Distinguishes solution symmetries from constraint symmetries and shows they are fundamentally different.

David Cohen, Peter Jeavons, Christopher Jefferson, Karen E. Petrie, Barbara M. Smith. Constraint Symmetry and Solution Symmetry. AAAI 2006, 21(2), p. 1589. PDF

Alan M. Frisch, Christopher Jefferson, Ian Miguel. Symmetry Breaking as a Prelude to Implied Constraints: A Constraint Modelling Pattern. ECAI 2004, pp. 171. PDF

Alan M. Frisch, Christopher Jefferson, Ian Miguel. Constraints for Breaking More Row and Column Symmetries. CP 2003, pp. 318–332. PDF

: Extends row and column symmetry breaking constraints for matrix models.

Puzzles and Games

Thomas Lofaro, Ruth Hoffmann, Miriam Sturdee, Christopher Jefferson, Alice Lynch. Understanding How Players Solve Puzzles. Workshop on Explanations with Constraints and Satisfiability, 2025. PDF

Ruth Hoffmann, Özgür Akgün, Christopher Jefferson. Composable Constraint Models for Permutation Enumeration. Discrete Mathematics & Theoretical Computer Science 26(1), 2025. PDF

: Constraint programming as a tool for exploring permutation patterns. Extends known enumeration counts for 1324-avoiding permutations to length 16.

Alice Lynch, Christopher Jefferson, Uta Hinrichs. Considering the Person in the Puzzle: Challenging Common Assumptions about Sudoku Player Strategies. DiGRA 2022. PDF

Joan Espasa, Ian P. Gent, Ruth Hoffmann, Christopher Jefferson, Alice M. Lynch, András Salamon, Matthew J. McIlree. Using Small MUSes to Explain How to Solve Pen and Paper Puzzles. arXiv:2104.15040, 2021. PDF

: Demystify: human-interpretable step-by-step puzzle explanations using Minimal Unsatisfiable Subsets. Matches human puzzle experts’ guides 89% of the time.

Christopher Jefferson, Wendy Moncur, Karen E. Petrie. Combination: Automated Generation of Puzzles with Constraints. SAC 2011, pp. 907–912. PDF

Ian P. Gent, Christopher Jefferson, Tom Kelsey, Inês Lynce, Ian Miguel, Peter Nightingale, Barbara M. Smith, S. Armagan Tarim. Search in the Patience Game ‘Black Hole’. AI Communications 20(3), pp. 211–226, 2007. PDF

Christopher Jefferson, Angela Miguel, Ian Miguel, S. Armagan Tarim. Modelling and Solving English Peg Solitaire. Computers & Operations Research 33(10), pp. 2935–2959, 2006. PDF

Combinatorics and Algebra

Sophie Huczynska, Christopher Jefferson, Struan McCartney. Digraph-defined External Difference Families and New Circular External Difference Families. arXiv:2504.20959, 2025. PDF

Sophie Huczynska, Christopher Jefferson, Silvia Nepšinská. Strong External Difference Families in Abelian and Non-abelian Groups. Cryptography and Communications 13(2), pp. 331–341, 2021. PDF

: Extends SEDFs from abelian to all finite groups. First non-abelian SEDFs constructed, with computational enumeration for all groups up to order 24.

Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne, Martin Leuner. On the Generation of Rank 3 Simple Matroids with an Application to Terao’s Freeness Conjecture. SIAM Journal on Discrete Mathematics 35(2), pp. 1201–1223, 2021. PDF

: Parallel algorithm for generating all non-isomorphic rank 3 simple matroids. Verifies Terao’s freeness conjecture for rank 3 arrangements with 14 hyperplanes.

Andreas Distler, Christopher Jefferson, Tom Kelsey, Lars Kotthoff. The Semigroups of Order 10. CP 2012, pp. 883–899. PDF

: Uses constraint programming to enumerate all semigroups of order 10.

Gregory V. Bard, Nicolas T. Courtois, Christopher Jefferson. Efficient Methods for Conversion and Solution of Sparse Systems over GF(2) via SAT-Solvers. Cryptology ePrint Archive, 2007/024, 2007. PDF

: Methods for solving sparse polynomial systems over GF(2) using SAT solvers, with applications to cryptanalysis.

Complexity and Applications

Ian P. Gent, Christopher Jefferson, Peter Nightingale. Complexity of n-Queens Completion. Journal of Artificial Intelligence Research 59, pp. 815–848, 2017. PDF

: Proves n-Queens Completion is both NP-Complete and #P-Complete. Shows a phase transition for random instances.

Peter Mann, V. Anne Smith, John B.O. Mitchell, Christopher Jefferson, Simon Dobson. An Exact Formula for Percolation on Higher-Order Cycles. arXiv:2102.09261, 2021. PDF

: Exact solutions for the giant connected component of graphs composed of higher-order homogeneous cycles following bond percolation.

Peter Mann, V. Anne Smith, John B.O. Mitchell, Christopher Jefferson, Simon Dobson. Exact Formula for Bond Percolation on Cliques. Physical Review E 104(2), 024304, 2021.