EPSRC logo

Details of Grant 

EPSRC Reference: EP/Y000609/1
Title: Enhancing Group Search with Graph Techniques
Principal Investigator: Hoffmann, Dr R
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Martin Luther Univ of Halle-Wittenberg Technical University of Kaiserslautern
Department: Computer Science
Organisation: University of St Andrews
Scheme: Standard Research - NR1
Starts: 01 December 2023 Ends: 30 November 2025 Value (£): 165,165
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
Information Technologies
Related Grants:
Panel History:
Panel DatePanel NameOutcome
17 May 2023 ECR International Collaboration Grants Panel 1 Announced
Summary on Grant Application Form
Group theory is a field in mathematics which investigates algebraic structures called groups, which can be used to describe the symmeties of any object. Thus, group theory has wide-reaching applications in virology, quantum computing, cyber security and communications theory. Groups are also used in finding and reducing symmetries within search problems, which is vital in modern Artificial Intelligence. So finding groups, their properties and computing fundamental group operations as fast as possible, is at the core of many UK world leading research areas and will have wide reaching impact in economic successes.

There is an inherit circular improvement that will come from the research in algorithms in group theory, as one of the computational techniques used in finding subgroups, their properties or computing operations is a type of search algorithm itself. Thus, improving search in groups will improve the search for other applications as well.

The current search techniques in groups are advanced but are still struggling with scaling issues. We are proposing to use search techniques commonly used in graph search problems and apply them to group theoretical search algorithms. Such techniques are

(1) (learned) nogood clauses during search which then will inform further search steps,

(2) restarting the search from the top at well defined intervals, and

(3) using weighted orderings on the search decisions.

We have found that using these techniques in graph problems sped up the search by at least two orders of magnitude. We expect the performance improvements to be the same or better across the board in group problems.

Further, these techniques allow for a simple way of parallelising the current sequential algorithms, without the need to design/engineer a whole new algorithm. Speeding up algorithms which solve group problems and enabling them to be easily parallelisable will further impact applications such as virology, where group theory is used to describe the structural and geometrical properties of viruses.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.st-and.ac.uk