skip to content

Backtrack Search in Permutation Groups

Presented by: 
Christopher Jefferson
Friday 31st January 2020 - 11:30 to 12:20
INI Seminar Room 1
While there are many problems can be solved in polynomial time, some important fundamental problems can only be solved by backtrack searches, which are often exponential time. These include many important permutation group problems including group and coset intersection, stabilizer, normaliser, and canonical image problems.  

This talk will give an overview of backtracking algorithms in permutation groups, explaining both the fundamental ideas, and the most improvements. In particular this will cover Leon's Partition Backtrack algorithm and the more recent Graph Backtracking algorithm.  

[This talk includes joint work with Rebecca Waldecker, Wilf Wilson and others]
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons