Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

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

Hongyang Zhang hongyang90 at gmail.com
Mon Jul 31 21:33:22 PDT 2017


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>


More information about the theory-seminar mailing list