The Centre for Interdisciplinary Research in Computational Algebra (CIRCA) was established in 2000 to foster new and existing collaborative research between members of the Schools of Computer Science and of Mathematics and Statistics in the area of computational abstract algebra.

The Centre undertakes mathematical research with computer assistance, develops new techniques for computation in abstract algebra and develops and distributes software implementing these techniques. This work is supported by research grants from EPSRC, the Leverhulme Trust, the Royal Society, the British Council, the European Commission and the Royal Society of Edinburgh.

The Centre also organises conferences, seminars and training courses and plays a significant role in the international efforts to develop maintain and promote the GAP (groups, algorithms and programming) software package, a leading integrated system for computational discrete mathematics and algebra.

News and Events

CIRCA seminar 30th November

There will be a CIRCA seminar on November 30th, at 1pm on Theatre D of Maths. Peter Cameron and Richard Connor will speak.

Peter’s title is “When is the commuting graph split or threshold?”.

Abstract: The commuting graph of a group (or semigroup) G has vertex set G, two vertices joined if they commute. It was introduced by Brauer and Fowler in 1955, in their seminal work on involution centralisers in simple groups.
Split graphs and threshold graphs are two subgraph-closed graph families arising in operations research. A graph is split if the vertex set is the union of a complete graph and a null graph (with maybe some edges between); it is threshold if there are vertex weights and two vertices are joined if the sum of their weights exceeds a threshold.
I hope to present the complete proof of the classification of groups whose commuting graph is split or threshold: they are either abelian, or generalised dihedral of twice odd order.

Richard’s title is “Similarity search by graph navigation: some high-dimensional problems”

Abstract: Similarity search is a simple concept: to (efficiently) find, from within a (very) large collection, those objects which are most similar to a query object presented from the same domain. We (kind of) know that even approximate search becomes linear-time when the data is “high dimensional”, and linear time is no use to us! Unfortunately, “high” means something like over 20 Euclidean dimensions, and our main current interest is in searching embeddings, which are high-dimensional vectors arising from convolutional neural networks (such as GPT.) Language model embeddings have thousands of dimensions.

Some interesting recent systems have emerged which use novel graph navigation techniques. Simply, each element of the collection is represented as a graph node, and nodes are connected according to some relation. Search strategy is something like: start at a random node and navigate the graph, at each step moving closer to the query, which should thus be reached in a logarithmic number of steps. The current “state-of-the-art” is hnswlib (Hierarchical Navigable Small-World), which claims to work independently of dimensionality.

That, of course, isn’t true! In this talk, we examine the essential concepts presented by the authors, and some unfortunate properties of high-dimensional spaces which spoil the low-dimensional intuitions of graph navigation.

All welcome!

CIRCA seminar 16th November

There will be a CIRCA seminar on 16th November, at 1pm in Theatre D of Maths.

Mun See Chang will speak on “Enriching Transformations for Dependently Typed Languages”.

Ursula Martin will speak on “The Social Machine of Mathematics”

Ursula’s abstract is: How does mathematics come about? In this talk I’ll look at what philosophers, social scientists and historians can tell us about what we are doing when we do mathematics, including recent work on explanation in mathematics, and on how mathematics has impact. I’ll also highlight new approaches to collaborative mathematics, computer supported formal proof, and AI-assisted proof, which challenge our understanding of what a proof might be.

All welcome!