Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

6 June 2018, Algebra|Coalgebra Seminar, Jouke Witteveen

Speaker: Jouke Witteveen
Title: Fine-Grained Computational Complexity
Date: Wednesday 6 June 2018
Time: 16:00-17:00
Location: Room F1.15, ILLC, Science Park 107, Amsterdam

Classically, complexity theory focuses on the hardest instances of a given length. A set is in P if there is a decision procedure for it that runs in polynomial time even on the most difficult-to-decide instances. Parameterized complexity theory, on the other hand, looks at the identification of easy instances. In this talk, we shall define parameterizations as independent objects and show that the class of parameterizations naturally forms a lattice. The parameterizations that put a given set in any of the standard parameterized complexity classes are filters in this lattice. From these insights, we conjecture a separation property for P.

For more information, see http://events.illc.uva.nl/alg-coalg or contact Frederik Lauridsen at .

Please note that this newsitem has been archived, and may contain outdated information or links.