Monday, July 13

Parameterized Complexity

10:30 AM-12:30 PM
Room: Sidney Smith 2135

This minisymposium will focus on parameterized complexity, including recent concrete complexity results and techniques, structural aspects, and open problems. The field is motivated by the many concrete problems that are NP-complete or worse, yet can be solved in polynomial time with only an additive exponential contribution from some limited distributional aspect(s) of the problem (the parameter). The theory is built around this sharper analysis of feasibility extending polynomial time and includes distinctive and powerful algorithmic techniques to exploit parameterization. It is widely embodied in practical exponential heuristics, and involves a rich and concretely applicable structure theory based on miniaturizations of Cook's and other theorems.

Organizer: Michael R. Fellows
University of Victoria, Canada
10:30 Parameterized Complexity, Overview and Open Questions
Rodney G. Downey, Victoria University, New Zealand
11:00 Parametric Tractability Techniques
Venkatesh Raman, The Institute of Mathematical Sciences, India
11:30 Structural Aspects of Parameterized Complexity
Kenneth W. Regan, State University of New York, Buffalo
12:00 Concrete W Hardness Results: The Challenges of Intricate Gadgeteering
Michael T. Hallett, ETH-Zentrum, Switzerland
Program Program Overview Program-at-a-Glance Program Updates Speaker Index Registration Hotel Transportation

MMD, 5/29/98