BREAKING NEW GROUND ON ALGORITHMIC FRONTS

Professor Michael Fellows and his University of Bergen research team are revolutionizing how some of computing’s greatest challenges are approached, through the use of new directions in algorithm design.

Parameterized Complexity has brought algorithmic theory into the modern era.  Today, no one would consider ignoring the structure and parameters of problems.  The development of sophisticated parameterized algorithms and innovative mathematical approaches allows complex questions and ‘big data’ to be analysed from new perspectives. The current challenge Professor Fellows has embraced is to combine this world-leading research with new complexity theory to understand the effectiveness of practical heuristics on real-world datasets, and to systematically design and improve heuristics, based on theory and experiments.

Some of the impactful approaches he is developing include turbocharging heuristics with FPT modules. Fellows’ program of reverse kernelization involves incorporating where the data comes from. Together with data visualization, this can significantly contribute to “big data” analysis. It is inevitable that there should be a theory of groovy FPT. The theme here is paying attention to the Structure of Argumentation, such as induction or minimum counter-example. The research answers questions as to how much axiomatic power do you need to prove a particular theorem or to support theorems in computational complexity or multivariate analysis.