[DMANET] Online Seminar Series on Frontiers of Parameterized Complexity: May 21, 2020 -- Michal Pilipczuk + Subscription to the Mailing List

This is the announcement of this week's talk in the online seminar
series on 'Frontiers of Parameterized Complexity'. *Please note that
further announcements of the talks in this series will be sent only to
the mailing list of this series. To subscribe to the mailing list
please send a mail to roohani@imsc.res.in with subject line 'Subscribe
Frontiers PC'.* The information about the upcoming talks can also be
found here https://frontpc.blogspot.com/2020/04/talks-schedule.html.

The link to join the meeting on Zoom is https://uib.zoom.us/j/4231169675
Meeting ID: 423 116 9675
Password: Name of the W[1]-complete problem, 6 letters, all capital.
Also known as a set of pairwise adjacent vertices.

This week's talk details are given below.

Speaker: Micha\l Pilipczuk, University of Warsaw

Title: Beyond Sparsity

Abstract: The last decade has witnessed impressive progress on the
understanding of structure in sparse graphs. Much of this progress can
be attributed to the systematic exploration of abstract definitions of
structural sparsity --- concepts of bounded expansion and nowhere
denseness. From the parameterized perspective, these two notions have
brought new techniques to the toolbox and helped to explain the
parameterized complexity of problems definable in First Order logic.
However, the contemporary graph theory offers multiple quantitative
notions (aka parameters) of "well-structuredness" that reach beyond
sparse graphs. To name just a few, we may bound the rankwidth of a
graph, exclude a vertex-minor, or stipulate VC parameters like VC
dimension or VC density. In the talk we will survey the recent
advances in lifting the developments of sparsity to classes of
well-structured dense graphs. We will particularly focus on
connections with concepts from model theory: stable and NIP classes,
and the notion of FO transductions.

********************************************************

The recordings of the past talks of this seminar series can now be
found at our newly launched YouTube channel 'Frontiers of
Parameterized Complexity'
https://www.youtube.com/channel/UCdfML-PShQNSCeqbz9Ol_oA.

Upcoming talks in the series include:

May 28 2020:
Speaker: D\'aniel Marx, Max-Plack-Institut f\"ur Informatik
Title: Incompressibility of H-free edge modification problems: Towards
dichotomy

June 04 2020:
Speaker: Hans Bodlaender, Utrecht University
Title: Typical Sequences Revisited - Computing Width Parameters of Graphs

June 11 2020:
Speaker: TBA
Title: TBA

June 18 2020:
Speaker: Martin Grohe, RWTH Aachen University
Title: Polylogarithmic Parameterized Algorithms for the Graph
Isomorphism Problem: From Bounded Degree to Excluded Minors

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/
*
**********************************************************