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 April 11th

The last CIRCA seminar of the semester will be on April 11th. Ian Gent and Jiaping Lu wil speak.

Jiaping’s title Generation of Iterated Wreath Products of Almost Simple Groups

Ian’s title Dominances in Single Player Games

Ian’s abstract Recently we have spent much time thinking about how to model and solve single player games using constraint solving and planning. Examples are patience/solitaire card games and also the classic arcade puzzle game Puzznic. For these games a key technique to reduce search is to exploit “dominances”. A dominance is a situation where we can ignore considering some moves because they are dominated by other possibilities: the ignored moves might lead to a solution but if they do the dominant moves must do as well. I will talk about the kinds of dominance that arise in these games.

CIRCA seminar March 28th

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

David Stewart (University of Manchester) will speak.

Title: You need 27 tickets to guarantee a win on the UK National Lottery (Jt with David Cushing)

Abstract: The authors came across the problem of finding minimal lottery design numbers j=L(n,k,p,t); that is, a set B_1, …, B_j subsets of {1,..,n} each of size k, such that for any subset D of {1,..,n} of size p, one finds an intersection D\cap B_i with at least t elements. In the context of a lottery, n represents the. number of balls, k the number of choices of balls on a ticket, p the size of a draw.
For the UK national lottery, n=59, k=p=6 and one gets a (rather meagre) prize as long as t is at least 2.
Using the constraint solving library in Prolog, we calculated j for k=p=6, t=2 and n all the way up to 70. For example L(59,6,6,2)=27. This is the second paper where we have aimed to show the value of Prolog and constraint programming in pure mathematics.
I’ll give an overview of constraint programming, logic programming in Prolog, and describe how we used these tools to solve the problem described in the title.