From parameterized complexity to recognizing 2-spheres

SPEAKER: Dr William Pettersson, RMIT University
Date: Friday 12th May
Time: 3:00am–4:00pm (Talk & Q/A)
Venue: Building 8 Level 9 Room 66 (AGR)
RMIT City campus
The seminar will be followed by snacks and drinks
All students and staff are welcome


ABSTRACT: Complexity theory studies the asymptotic running times of algorithms as a function of how big a given problem is. However, especially in combinatorial problems, the difficulty does not always come solely from the size of a problem. Parameterised complexity is one way in which we can study algorithms and determine exactly which aspects of a given instance makes the problem hard. This not only gives more insights into the problem, but often leads to algorithms which are far faster in real-world applications. In this talk I will give a background on complexity theory and parameterised complexity that is aimed at those new to the field. This will include a brief overview of basics such as big-oh notation, as well as explanations of common techniques used in complexity theory before going into parameterised complexity. We will finish by hopefully demonstrating that it is “hard” to recognise a 2-dimensional sphere
BIO: William is a Research Fellow at RMIT University, where he works on the cross-over between topology and optimisation. Since receiving his PhD from the University of Queensland in 2014, where he studied computational graph theory, he has worked in computational topology looking at quantum invariants of manifolds and the census enumeration problem. Across all his work he has consistently looked at problems and said “Surely it’d be faster to tell a computer to do that” and so far it seems he has been mostly right.



Skip to toolbar