CIRCA

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 February 22nd


There will be a CIRCA lunchtime seminar on 22nd Feb at 1pm in Theatre D of Maths.

Chris Brown and Victoria Ironmonger will speak.

Chris’s Title: Semi-Automatic Ladderisation: Improving Code Security through Rewriting and Dependent Types
Chris’s Abstract: Cyber attacks become more and more prevalent every day. An arms race is thus engaged between cyber attacks and cyber defences. One type of cyber attack is known as a side channel attack, where attackers exploit information leakage from the physical execution of a program, e.g. timing or power leakage, to uncover secret information, such as encryption keys or other sensitive data. There have been various attempts at addressing the problem of side-channel attacks, often relying on various measures to decrease the discernibility of several code variants or code paths. Most techniques require a high-degree of expertise by the developer, who often employs ad hoc, hand-crafted code-patching in an attempt to make it more secure. In this talk, we take a different approach: building on the idea of ladderisation, inspired by Montgomery Ladders. We present a semi-automatic tool-supported technique, aimed at the non-specialised developer, which rewrites (a class of) C programs into functionally (and even algorithmically) equivalent counterparts with improved security properties. Our rewriting mechanism provides refactorings that transform the source code into its ladderised equivalent, driven by an underlying verified rewrite system, based on dependent types. Our rewrite system automatically finds rewritings of C programs producing their equivalent ladderised counterparts for a subset of C. We demonstrate our ladder rewriting technique on a number of representative examples from the cryptographic domain, showing increased security thanks to the process.

Victoria’s Title: The atomicity problem for equivalence relations and other structures
Victoria’s Abstract: An atomic poset is one which cannot be expressed as a union of two proper subsets. Atomic sets are sometimes called ideals, and atomicity is equivalent to the joint embedding property. We look at posets where two combinatorial structures are related when one is a substructure of the other. Given such a poset, avoidance sets are subsets defined by their forbidden substructures. The atomicity problem asks whether it is decidable, given a finite set, whether its avoidance set is atomic. We will discuss the atomicity problem for various structures, finishing by solving it for equivalence relations under the non-consecutive order. In this, we show that an avoidance set is atomic if and only if each forbidden element has only one class size.


CIRCA seminar February 8th


There will be a CIRCA lunchtime seminar on 8th Feb at 1pm in Theatre D of Maths.

Coen del Valle and Ruth Hoffmann will speak.

Coen’s title: It’s not always bad to be greedy
Coen’s abstract: A base for a group of permutations of a set \Omega is a subset of \Omega whose pointwise stabiliser contains only the identity permutation. In this talk we discuss a natural greedy algorithm for building a base. In 1999, Cameron conjectured that there is some absolute constant, c, such that for any primitive group, G, every greedy base for G has size at most c times that of a minimum base for G. We discuss new results towards a proof of this conjecture, namely that it holds whenever G is either symmetric or alternating, except for a class of possible exceptions. Time permitted we may also describe an interesting application in graph theory.

Ruth’s title: Composable Constraint Models for Permutation Pattern Enumeration Problems
Ruth’s abstract: I will give an introduction to permutation patterns, discuss a few pattern types as well as porperties and show on an example how constraint programming has helped breaking the current state of the art (specialised) methods to enumerate permutation pattern problems.
In particular we will look at the 1324 avoiding permutations for which to date there still is no defined growth function. We progressed the enumeration for 1324 avoiding permutations with some additional properties/constraints (namely permutations with a fixed number of inversions) and identified a unique sequence in the OEIS to this problem. This was made possible through the creation of a library of constraint models for many of the permutation pattern types, properties and statistics. This library was created with composability in mind, so that we can offer mathematicians a neat ‘copy and paste’ library from which they can create their own bespoke model for the permutation pattern problems with a selection of properties.