|
Theory Seminar: Practical Fixed-Parameter Tractability and Foundations of Kernelization
Rod Downey
Victoria University, Wellington New Zealand
Tuesday, April 15, 2008
1:30 p.m., 2310 CS
Abstract:
Fixed-paraneter tractability is an approach to
combinatorial problems which allows one to try to address
complexity for practical computation. Likely the most
important technique is kernelization or pre-processing.
This talk looks at recent work which allows one to
show that no small kernels are possible assuming some reasonable
complexity hypothesis.
This talk will be accessible to graduate students.
|
