[DMANET] Online Seminar on Frontiers of Parameterized Complexity Upcoming Talk: August 13, 2020 -- Kevin Pratt

We are back with our online seminar series on Frontiers of
Parameterized Complexity. We will resume the talks in this series
starting August 13, 2020 at 17:00 GMT+2 with a weekly frequency, that
is, we will have talks every Thursday at 17:00 GMT+2. The details for
joining the talks are given below.

The link to join the zoom talk is https://uib.zoom.us/j/4231169675.

Meeting ID: 423 116 9675
Password: Name of the W[1]-complete problem, six letters, all capital.
Set of pairwise adjacent vertices.

More details about the seminar series can be found here
https://frontpc.blogspot.com. If you wish to get notifications about
the next talks via email please send an email to roohani@imsc.res.in
with the subject line 'Subscribe FrontPC' (if you haven't already).

The details of the first upcoming talk are given below.

Date and time: August 13, 2020 at 17:00 GMT+2
Speaker: Kevin Pratt, Carnegie Mellon University

Title: Parameterized applications of multivariate polynomial differentiation
Abstract: The apolar inner product of two polynomials over a field is
defined as the dot product of their coefficient vectors (with
appropriate scaling). Specific instances of computing this inner
product lead to the fastest-known algorithms for several intractable
problems, including computing the permanent of a matrix and detecting
simple paths in a graph. In this talk I will explore two different
approaches for computing this inner product, one numeric and one
symbolic. I will show how these yield in a very general manner
non-trivial algorithms for problems such as detecting and
approximately counting simple paths in a graph. Our approaches raise
concrete algebraic questions that could provide a path to faster
algorithms for these (and other) problems.

Part of this talk is based on joint work with Cornelius Brand.

---------------------------------------------

Other upcoming talks in the series include:

August 20 2020:
Speaker: Pasin Manurangsi, Google Research
Title: TBA

August 27, 2020:
Speaker: TBA
Title: TBA

September 03 2020:
Speaker: Virginia Vassilevska Williams, Massachusetts Institute of Technology
Title: TBA

September 10 2020:
Speaker: Peter Garland, University of California Santa Barbara
Title: TBA

September 17 2020:
Speaker: Meirav Zehavi, Ben-Gurion University
Title: TBA

---------------------------------------------

For more details please contact one of the following.

Roohani Sharma: roohani@imsc.res.in
Saket Saurabh: saket@imsc.res.in
Fedor Fomin: Fedor.Fomin@uib.no

Best regards and cheers!


**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************