My UW | UW Search

Computer Science Home Page
[an error occurred while processing this directive] [an error occurred while processing this directive]

Theory Seminar: Practical Fixed-Parameter Tractability and Foundations of Kernelization

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. [an error occurred while processing this directive]