PARAMETERIZED COMPLEXITY RESEARCH UNIT (PCRU)

 

Professor Michael Ralph Fellows
Director, Parameeterized Complexity Research Unit

The Parameterized Complexity Research Unit (PCRU) conducts research within the framework of Parametized Complexity (PC), a rapidly emerging expansion of Algorithms and Complexity.  Real-world problems from Al, Computational Biology, Social Choice and others, give rise to computational problems that can be solved algorithmically.  The efficiency of algorithms has a direct impact on applications; for example, improved algorithms for clustering yield more accurate modelling of the health of deep sea fisheries.  Research in the PCRU has central aims as follows:

Algorithmics: design and analyse efficient algorithms that make use of problem structure in terms of parameters, to classify the parameterized complexity.

 

Modelling: analyse real-world problem instances systematically, to identify parameters that capture the structure of real-world problem instances.

 

Foundations: gain unifying insights into what makes a problem computationally hard or easy, develop new algorithmic techniques, and extend the two-dimensional parameterized framework to the fully multivariate framework.

 

Community: maintain an international interdisciplinary research network that connects researchers from different communities (AI, Algorithms, Computational Complexity, Computational Biology, Social Choice, Signal Processing, Quantum, Crypto).