[theory-seminar] [theory-lunch] Theory lunch 08/03 -- Josh Alman

[Hongyang Zhang]

Hi All

Theory lunch will happen as usual this Thursday at noon. We have Josh Alman
visiting from MIT as our speaker this week -- see the introduction below.

If you are interested in coming, it would be great if you RSVP so we get an
estimate of how much food to order -- everyone is welcome!

-------------------------------------------------------------------------
Title: Dynamic Parameterized Problems and Algorithms
Abstract: Fixed-parameter algorithms and kernelization are two powerful
methods to solve NP-hard problems. Yet, so far those algorithms have been
largely restricted to static inputs.

In this talk, I will tell you about fixed-parameter algorithms and
kernelizations for fundamental NP-hard problems with dynamic inputs. We
will consider a variety of parameterized graph problems which are known to
have f(k) * n^{1 + o(1)} time algorithms on inputs of size n, and consider
the question of whether there is a data structure that supports small
updates (edge/vertex insertions and deletions) with an update time of g(k)
* n^{o(1)}; such an update time would be essentially optimal. We will also
complement our positive results by several conditional and unconditional
lower bounds.

No prior knowledge about fixed-parameter tractability or dynamic algorithms
will be assumed!

Joint work with Matthias Mnich and Virginia Vassilevska Williams
-------------------------------------------------------------------------

-hongyang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20170731/ccabd5b1/attachment.html>