Parameterized Complexity Research Unit

Always Parameterize

Parameterized Complexity Research Unit

 

 

Parameterized Complexity Research Unit

Who we are

The Parameterized Complexity Research Unit is an independent research unit in the Charles Darwin University. Established in 2012, PCRU interacts with a broad international research community and undertakes research that is strongly interdisciplinary.

What is Parameterized Complexity?

Parameterized Complexity is a recent branch of computational complexity theory that provides a framework for a refined analysis of hard algorithmic problems. The big, important problems facing Planet Earth have structure with “secondary” measurements (parameters), apart from the primary measurement of overall input size, that significantly affect problem computational complexity.

The central notion of fixed parameter tractability (FPT) is a generalization of polynomial-time based on confining any non-polynomial (typically exponential) complexity costs to a function only of these secondary measurements.

Parameterized algorithms have strong connections to heuristics for NP-hard problems, and the multivariate approach allows more realistic modelling of real-world input distributions. The field is strongly interdisciplinary, with applications in massive parallel processing of huge data sets, bioinformatics, AI, computational social choice, ecology and other disciplines.

Key Research Themes

Multivariate Algorithmics

The big, important problems facing Planet Earth have structure with secondary measurements (parameters), apart from the primary measurement of overall input size, that significantly affect problem computational complexity.

Parameterized Complexity is a recent branch of computational complexity theory that provides a framework for a refined analysis of hard algorithmic problems.

The multivariate approach allows more realistic modelling of real-world input distributions.

Research is conducted in:

  • Foundational multivariate algorithmics; including for example, research into interconnections with heuristics and approximations.
  • Applications in analysing massive data sets, bioinformatics and biomedicine, artificial intelligence, computational social choice, cognitive science, ecology, and other disciplines.
  • Mathematical Sciences Communication

Our research explores ways of sharing the frontiers of mathematical science and our cutting-edge research, especially with children.

Building on work in the Computer Science Unplugged! project, the PCRU creates activities and materials with Both-Ways philosophy to better establish, maintain and nurture math learning in remote Indigenous and all communities.

 

Research Coordinator: Peter Shaw

Contact us

PCRU
Casuarina campus

  • T: 08 8946 6904
  • F: 08 8946 7098

E: pcru@cdu.edu.au