21st - 31st December, 2020
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
Scientific Coordinators
For registration, please fill this form.
For queries/suggestions please write to us at pcomplexity301@gmail.com