BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
BEGIN:VEVENT
UID:/NewsandEvents/Events/Upcoming-Events/newsitem
/9997/6-June-2018-Algebra|Coalgebra-Seminar-Jouke-
Witteveen
DTSTAMP:20180528T135037
SUMMARY:Algebra|Coalgebra Seminar, Jouke Witteveen
ATTENDEE;ROLE=Speaker:Jouke Witteveen
DTSTART:20180606T160000
DTEND:20180606T170000
LOCATION:Room F1.15, ILLC, Science Park 107, Amste
rdam
DESCRIPTION: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 t
hat runs in polynomial time even on the most diffi
cult-to-decide instances. Parameterized complexity
theory, on the other hand, looks at the identific
ation of easy instances. In this talk, we shall de
fine 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 co
mplexity classes are filters in this lattice. From
these insights, we conjecture a separation proper
ty for P.
X-ALT-DESC;FMTTYPE=text/html:\n Classically, c
omplexity theory focuses on the hardest instances
of a given length. A set is in P if there is a dec
ision procedure for it that runs in polynomial tim
e even on the most difficult-to-decide instances.
Parameterized complexity theory, on the other hand
, looks at the identification of easy instances. I
n this talk, we shall define parameterizations as
independent objects and show that the class of par
ameterizations naturally forms a lattice. The para
meterizations that put a given set in any of the s
tandard parameterized complexity classes are filte
rs in this lattice. From these insights, we conjec
ture a separation property for P.

\n
URL:http://events.illc.uva.nl/alg-coalg
CONTACT:Frederik Lauridsen at f.m.lauridsen at uva
.nl
END:VEVENT
END:VCALENDAR