CIRCA

News

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.