Duncan Adamson

Lecturer at the University of St Andrews

  Contact Information

Address: 109 Jack Cole Building
π Potato Ave, St Andrews KY16 9SX
United Kingdom
E-mail:   Duncan.Adamson@st-andrews.ac.uk
Photo

  About

I am currently a lecuturer in the school of computer science at the University of St Andrews. My main research interests are in combinatorics on words, algorthmims for combinatorial objects, and applying computational techniques to problems originating in Chemistry.

Before this, I was a Research Fellow and Theme Lead at the Leverhulme Research Centre for Functional Materials Design. Previously, I was a postdoctoral researcher working on problems in Combinatorics on words, in the Theoretische Informatik group, at the University of Göttingen, and before that I was a postdoctoral researcher at the Icelandic Centre of Excellence in Theoretical Computer Science at Reykjavik University studying distributed colouring problems. Prior to coming to Iceland, I was a postgraduate researcher at the Department of Computer Science in the Univeristy of Liverpool, in the algorithms and complexity research group. My PhD thesis is titled Algorithmic and Combinatorial Problems in Crystal Structure Prediction, supervised by Prof. Igor Potapov, with secondary supervisors Matthew Dyer and Vladimir Gusev. I was funded by the Leverhulme Research Centre for Functional Materials Design. I completed my undergraduate studies at the University of Glasgow, with my masters project supervised by David Manlove. A graph of my Mathematical Genealogy can be found here.

  Schedule (Semester 1, 2024 - 2025)

Rough outline of my scedule. Note this only includes fixed weekly events, I may be busy at other times due to one-off events, so if you want to organise a meeting please double check.
Time\Day Monday Tuesday Wednesday Thursday Friday
9:00 - 10:00 CS3302 CS3302
10:00 - 11:00 CS2001
11:00 - 12:00
12:00 - 13:00 Research
Meeting
CS2001 Research
Meeting
13:00 - 14:00 Supervisory
Meeting
Research
Meeting
14:00 - 15:00 CS3302
15:00 - 16:00
16:00 - 17:00

  Research Interests

Combinatorics on words: My interest on combinatorics on words has been primarily motivated on representing real world objects within a discrete space. In particular, I am been interested in capturing symmetry on words, such as reflective and, in the multidimensional setting, translational symmetries. Going forward I would like to extend more results from one dimension into the multidimensional setting.

k-centre problem for implicitly defined objects (such as graphs and words): Many classes of combinatorial objects can be represented as a weighted graph using some similarity measure to assign weights to the edges. For large graphs, for instance the set of all words of length n, generating the whole graph is impractical. To this end, we seek to take a set of representative samples from the graph. The idea behind the k-centre problem for implicitly defined graphs is to take k samples from some graph that allow the local properties to be determined. At present I have worked this problem for (multidimensional) words, using the overlap distance between subwords as the distance. Going forward, I would like to study more complex objects.

Crystal Structure Prediction: During my PhD I have focused on the problem of predicting the structures of Crystals from first principles. My main results has been on the hardness of this problem, and more recently on approaches to solving similarly motivated problems. Move forward I would like to show undecidability for the general version of this problem

Temporal Graphs: I have recently begun working on the problem of harmonious colourings in the setting of temporal graphs. The initial results have shown that this is a highly challenging problem, even when the underlying graph is a path. The next steps in the project would be to look at solutions to this problem when each time step has been solved.

Stable Matchings: During my Masters (dissertation is available here), I worked on the stable matching problem for incomplete lists with ties. My main result was providing new bounds on the number of blocking pairs for maximum matchings in this setting. Moving forward I would be interested in obtaining similar results for more complex settings such as the kidney exchange problem.

  Publications

A more in-depth overview is available on my dblp profile found here.
  1. Rollercoasters with Plateaus
    Duncan Adamson, Pamela Fleischmann, Annika Huch
    Presented at Reachability Problems (RP 2024).
  2. Harmonious Colourings of Temporal Matchings
    Duncan Adamson
    Winner of the best paper award at SAND 2024.
  3. Enumerating m-Length Walks in Directed Graphs with Constant Delay
    Duncan Adamson, Paweł Gawrychowski, Florin Manea
    Presented at LATIN 2024. Full version available on arXiv.
  4. Structural and combinatorial properties of 2-swap word permutation graphs
    Duncan Adamson, Nathan Flaherty, Igor Potapov, Paul G. Spirakis
    Presented at LATIN 2024. Full version available on arXiv.
  5. k-Universality of Regular Languages
    Duncan Adamson, Pamela Fleischmann, Annika Huch, Tore Koß, Florin Manea, Dirk Nowotka
    Presented at ISAAC 2023. Full version available on arXiv.
  6. Optimality guarantees for crystal structure prediction
    Vladimir V. Gusev, Duncan Adamson, Argyrios Deligkas, Dmytro Antypov, Christopher M. Collins, Piotr Krysta, Igor Potapov, George R. Darling, Matthew S. Dyer, Paul Spirakis, Matthew J. Rosseinsky
    Published in Nature 619.
  7. Longest common subsequence with gap constraints
    Duncan Adamson, Maria Kosche, Tore Koß, Florin Manea, Stefan Siemer
    Presented at WORDS 2023. Full version available on arXiv.
  8. Ranking and Unranking k-subsequence universal words
    Duncan Adamson
    Presented at WORDS 2023. Full version available on arXiv.
  9. Distributed Coloring of Hypergraphs
    Duncan Adamson, Magnús M. Halldórsson, Alexandre Nolin
    Presented at SIROCCO.
  10. The k-center Problem for Classes of Cyclic Words
    Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov
    Presented at SOFSEM 2023.
  11. The Complexity of Periodic Energy Minimisation
    Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov
    Presented at MFCS 2022.
  12. Ranking Binary Unlabelled Necklaces in Polynomial Time.
    Duncan Adamson
    Presented at DCFS 2022. Full version available on arXiv.
  13. Faster exploration of some temporal graphs.
    Duncan Adamson, Vladimir V. Gusev, Dmitriy Malyshev, Viktor Zamaraev
    Presented at SAND 2022.
  14. Ranking Bracelets in Polynomial Time.
    Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov
    Presented at CPM 2021. Full version available on arXiv.
  15. On the Hardness of Energy Minimisation for Crystal Structure Prediction.
    Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov
    Presented at SOFSEM 2020, Journal version published in Fundamenta Informaticae. Full version also available on arXiv.

  Talks

SAND 2024  Harmonious Colourings of Temporal Matchings
LATIN 2024   Enumerating m-Length Walks in Directed Graphs with Constant Delay
ISAAC 2023   k-Universality of Regular Languages
WORDS 2023   Ranking and Unranking k-Subsequence Universal Words
SOFSEM 2023   The k-Centre problem for necklaces
ACTO Group Seminar 2022   The k-centre problem for classes of necklaces
DCFS 2022   Ranking Binary Unlabelled Necklaces
SAND 2022   Faster Exploration Of Some Temporal Graphs
HI Mathematics Seminar Series 2022   Combinatorial Structures for CSP
CPM 2021   Ranking Bracelets in Polynomial time
BCTCS 2021   Ranking Bracelets in Polynomial time
BCTCS 2020   Multidimensional Necklaces: Enumeration, Generation, Ranking and Unranking
SOFSEM 2020   Crystal Structure Prediction by Vertex Removal in Euclidean Space
BCTCS 2019   Crystal Structure Prediction by Vertex Removal in Euclidean Space