CIRCA

News

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.

CIRCA seminar March 14th


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

Peiran Wu and Yayi Zhu will speak.

Peiran’s Title: Irredundant bases for classical groups

Peiran’s Abstract: Given a classical group G(V) over a finite field, a subgroup of G(V) is in Aschbacher class C_1 if it stabilises a subspace of V. I will talk about my ongoing search for bounds on irredundant bases of classical groups acting primitively with point stabilisers in C_1.

Yayi’s Title: Presentations for ideals in T_n
Yayi’s Abstract: The Green’s D relation on the full transformation semigroup T_n partitions T_n into n subsets, each containing all transformations of a certain rank. Any ideal I of T_n is a union of D-classes, and consists of all maps of rank 1, 2,…, m for some m no bigger than n. We investigate the presentations of the ideals. For some of them, we determine how large portion of their Cayley table is needed to define a ‘nice’ presentation.

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.

CIRCA seminar January 25th


The first CIRCA seminar of the year is on January 25th in Theatre D of Maths at 1pm.

Speaker: Carla Biermann
Title: Sampling solutions to constraint satisfaction problems
Abstract: State-of-the-art constraint programming solvers have become efficient in finding one solution to a specified problem. However, sometimes, users would like to choose a solution from multiple or inspect a sample of solutions without obtaining all solutions, especially when the solution space is large. This need gives rise to solution sampling, which aims to provide the user with an interesting sample of solutions. There are different measures of “interestingness” and algorithms that ensure certain sampling behaviours. I will present two such algorithms and the results of an experimental analysis of their performance on specific constraint satisfactory problems (CSPs). The findings aim to spark a discussion with the audience on more applications of solution sampling in CSPs for my fourth-year project.

and

Speaker: Nguyen Dang
Title: Automated algorithm configuration and algorithm selection
Abstract: Many algorithms have their own parameters that can impact the algorithm performance. Automated algorithm configuration is a family of general-purpose techniques that focuses on finding the best parameter setting of an algorithm for a given problem. Automated algorithm selection, on the other hand, is a closely related topic that helps us select the best algorithm among a given set of algorithms for a specific instance of a problem. Automated algorithm configuration and algorithm selection have got several successful applications across different domains. In this talk, I will first give a brief introduction to the two topics. The remaining part of the talk will be an open discussion with the audience to see if there are potential applications of those techniques on the GAP system.

Ruth Hoffman wins EPSRC grant


Ruth has just been awarded £199211 by EPSRC for a grant called “Enhancing Group Search with Graph Techniques”. The grant will run from now until July 2025. Congratulations Ruth!

Peter Cameron awarded the 2017 LMS Senior Whitehead Prize


Congratulations to Peter Cameron on being awarded the 2017 Senior Whitehead Prize of the London Mathematical Society! The prize is awarded for ‘exceptional research contributions across combinatorics and group theory, his fertile imagination and encouragement of others having sparked activity in many fields’. He became the third person to win both a Junior and Senior Whitehead Prize. Please read further details in the LMS announcement and in this post in Peter Cameron’s blog.

New grant for Sophie Huczynska


Sophie Huczynska has been awarded a Carnegie Trust Research Incentive Grant on the topic of ‘Difference Families in Coding and Cryptography’. This will support a collaboration with Maura Paterson at Birkbeck, University of London, and Siaw-Lynn Ng at Royal Holloway, University of London.