Parameterized Complexity 301

A Workshop on Parameterized Complexity


21st - 31st December, 2020

Link for registration: form

Honorary Speaker: Professor Michael Fellows
Elite Professor of Computer Science
Department of Informatics
University of Bergen.
Talk Schedule: 30th December 2020, 2pm IST.
Title: An Account of the Origins and History of Parameterized Complexity
Abstract: The talk will give an account of the intellectual origins and historical development of the field of parameterized/multivariate algorithms and complexity theory, highlighting with concrete examples the various historical points. The account is necessarily somewhat opinionated and anecdotal (an oral history) and from the point of view of one of the founders of the field, and will include some advices for young researchers entering the area. The account will be broad-brush, with some ideas about principle directions in which the field might continue to develop.


This workshop will start by defining the basic notions in parameterized complexity, introduce some basic methods in both designing parameterized algorithms as well as show such algorithms are not possible. However, the main objective is to cover some new directions where the research is taking place. Topics that we will cover are


  • Advance Kernelization, including Lossy Kernelization

  • Graph Decompositions and Recursive Understanding

  • Computational Social Choice

  • FPT Approximation including for Counting Problems

  • FPT Streaming and Dynamic Algorithms

  • FPT in Computational Geometry

  • Graph Contractions: Old and New Developments

  • Survey on New Results that has happened over last couple of years

A series of nine mini-workshops on introductory topics in parameterised algorithms, including branching, important separators, matroids, tree width, and parameterized intractability. These will be held over the next nine Saturdays virtually over Google Meet, from 2:15PM onwards. The sessions will be run as watch parties of relevant YouTube lectures, and discussions of problems will be interleaved into the lectures. More specifics can be found on the event website:

http://www.tinyurl.com/PC301prep

We expect that these sessions will be particularly useful as preparatory material for those who plan to attend the PC 301 workshop but need a refresher on the introductory materials. A link with preliminary details for the PC 301 workshop.

Preliminary Topics can be found on the following links:

https://sites.google.com/view/sakethome/teaching/parameterized-complexity

https://www.youtube.com/playlist?list=PLzdZSKerwrXpr6hWq1s63a42YbkocAK1Q

Following link has a good detail of information on reference material, books, research and other related stuff in parameterized complexity: http://fpt.wikidot.com/

Dates for PC301: December 21- 31, 2020

Venue: Online Platforms

List of Speakers:

Akanksha Agrawal, IIT Madras

Fedor V. Fomin, University of Bergen

Petr Golovach, University of Bergen

Karthik C. S., New York University

Daniel Lokshtanov, University of California Santa Barbara

Dániel Marx, CISPA Helmholtz Center for Information Security

Neeldhara Misra, IIT Gandhinagar

Fahad Panolan, IIT Hyderabad

Marcin Pilipczuk, University of Warsaw

Michał Pilipczuk, University of Warsaw

M. S. Ramanujan, University of Warwick

Saket Saurabh, IMSc

Roohani Sharma, MPII

Vaishali Suryanarayanan, University of California Santa Barbara

Prafullkumar Tale, CISPA Helmholtz Center for Information Security

Meirav Zehavi, Ben Gurion University of the Negev



For registration, please fill this form.
For queries/suggestions please write to us at pcomplexity301@gmail.com