Department of Mathematics
Title : Recent Advances in Multivariant Algorithmics
| Speaker: Rod Downey Affiliation: Victoria University of Wellington Time: 3:00 pm Thursday, 30 May, 2013 Location: MLT3 |
Abstract
| Parameterized complexity was born in the 1990's as an attempt to design a complexity theory to explain unexpected efficient behaviour in algorithms and to try to develop a complexity theory more attuned to real life algorithmics. The idea is that in real life few problems come only presented by size (which is the assumption for classical complexity). They all have parameters, shape, dimension, colour limitations, genus, etc. We can use the multivariant nature of problems to deconstruct the apparent intractibility of such problems. Deconstructing intractability to seek and limit causes of exponential blow-up seems a noble cause. The last decade has seen this dialog with computational problems get close to the dream of complexity theorists where lower bounds match upper bounds of problems, or course modulo complexity assumptions. Moreover, we even know what kinds of tools are likely to be successful. I will try to describe these developments, and point at a number of important and interesting problems. |
-
Programmes and Centres
- New Zealand Institute of Mathematics and its Applications (NZIMA)
- Community for Understanding and Learning in the Mathematical Sciences (CULMS)
- Centre for Mathematical Social Science (CMSS)
- Department of Computer Science
- Department of Engineering Science
- Department of Physics
- Department of Statistics
- Auckland Bioengineering Institute
