Welcome
logo_n_k.bmp

The PARAMETERIZED COMPLEXITY COMMUNITY WIKI. WELCOME

The field is growing by leaps and bounds—Herein you will find applications, open problems, the 'FPT Races' Table, the FPT Newsletter, and resources including courses about parameterized complexity and open positions. Witness the growth of the field. Follow the news on facebook with @MikeFellowsFPT and subscribe to Youtube FPT Complexity.


Round the World Relay in Combinatorics, Tuesday June 8, 2021

See 22 interesting talks: http://people.maths.ox.ac.uk/scott/relay.htm

World.jpg

An international "Round the World Relay in Combinatorics" will take place on Tuesday June 8, 2021. There will be 22 seminars, hosted by different groups around the world. The day will start in Australia at 2am UTC and end in Alaska at 11pm UTC. Stops along the way include Brazil, Canada, Chile, China, Czech Republic, France, Hungary, New Zealand, Poland, Russia, South Korea, the United Kingdom, and the USA. Each site will host a talk, and everyone is welcome!

Thanks to Balazs Keszegh for designing the poster.

If you have any questions, then please get in touch with Alex Scott (Email: lastname at maths.ox.ac.uk), who is coordinating the event.


AAAC 2021 —- The 14th Annual Meeting of Asian Association for Algorithms and Computation
October 22-24, 2021, Tainan, Taiwan

http://aaac2021.ie.nthu.edu.tw/ The official website of AAAC is http://www.aa-ac.org.

All areas of theoretical computer science, especially design and analysis of algorithms and complexity theory.

SUBMISSION: Submit one-page (A4) abstracts (in pdf format) that can be based on original results or surveys of existing results. Informal working notes including the one-page abstracts will be distributed at the meeting, which does not prevent any form of future publication of the same work. All submissions should be made electronically. Papers are now being accepted through the EasyChair Conference System. https://easychair.org/conferences/?conf=aaac2021

BEST STUDENT PAPER AWARD: Indicate if you are a student.

DATES: One-page abstract submission due: July 23 (Fri), 2021 (AoE)

Keynote Speeches:
Kazuo Iwama (Kyoto University, Japan)
Luca Trevisan (Bocconi University, Italy)
Prudence Wong (University of Liverpool, UK)

Tutorial:
Evanthia Papadopoulou (University of Lugano, Switzerland)


47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021)
https://wg2021.mimuw.edu.pl/

The conference will take place on 23-25 June as an online event.
Registration is free but mandatory; the deadline is June 19, 11.59 PM AoE.

The conference will have three invited talks:
Vida Dujmovic (Ottawa): Graph product structure theory,
Wojciech Samotij (Tel Aviv): On a method of enumerating independent sets,
Édouard Bonnet (Lyon): Twin-width,
and 30 contributed talks.

On Fri, June 25 there will also be a special session dedicated to the memory of the late Dieter Kratsch, who for many years served as a member of WG Steering Committee.

We hope to see you during talks (and social events)! Pawel Rzazewski


IPEC: The International Symposium on Parameterized and Exact Computation (IPEC) is an annual conference covering all aspects of parameterized and exact algorithms and complexity. Its 16th edition will be part of ALGO 2021, which also hosts ESA 2021 and a number of more specialized conferences and workshops. ALGO 2021 will take place on September 6-10, 2021, Lisbon, Portugal. Due to the COVID-19 pandemic, IPEC might be held online.

Webpage: http://algo2021.tecnico.ulisboa.pt/IPEC2021/index.html <http://algo2021.tecnico.ulisboa.pt/IPEC2021/index.html>

Papers presenting original research in the area are sought, including but not limited to:
- new techniques for the design and analysis of parameterized and exact algorithms;
- fixed-parameter tractability and kernelization results;
- parameterized complexity theory;
- parameterized (in)approximability results;
- relationships between parameterized complexity and traditional complexity classifications;
- applications of parameterized and exact computation;
- implementation issues of exact, parameterized, and kernelization algorithms;
- theoretically grounded studies on parameterized and exact computations and kernelization for real-world applications and algorithmic engineering.

SPECIAL EVENTS
NERODE: An invited talk is planned by the 2021 EATCS-IPEC Nerode Prize winner.
PACE: Special session for the 5th Parameterized Algorithms and Computational Experiments Challenge (PACE 2021) awards.

A special issue of Algorithmica is planned for selected papers presented at IPEC 2021.

SUBMIT FOR BEST STUDENT PAPER AWARD: Best Paper Award and a Best Student Paper Award, both of which may be exceptionally split between two or more papers. A student is someone who has not received a PhD degree before the full paper submission deadline. A paper accepted to the conference is eligible for the Best Student Paper Award if either all its authors are students, or besides student co-author(s) there is one non-student co-author that confirms, at the moment of submission, that a clear majority of conceptual work on the paper was done by the student co-author(s). In the latter case, it is moreover expected that a student gives the presentation at the conference. Papers co-authored by members of the program committee are not eligible for the Best Paper Award or the Best Student Paper Award.

DATES
Paper Registration: June 25, 2021 (23:59 AoE)
Notification of acceptance: July 30, 2021
Conference dates: September 8-10, 2021

PROGRAM COMMITTEE
Akanksha Agrawal, IIT Madras, India
Fahad Panolan, IIT Hyderabad, India
Dimitrios Thilikos, LIRMM, Universite de Montpellier, CNRS, France
Eduard Eiben, Royal Holloway, University of London, UK
Ignasi Sau, LIRMM, Universite de Montpellier, CNRS, France
Jesper Nederlof, Utrecht University, Netherlands
Jiehua Chen, Vienna University of Technology, Austria
Karl Bringmann, Saarland University, Germany
Karthik C. S., New York University, USA
Martin Koutecky, Charles University, Czech Republic
Meirav Zehavi (co-chair), Ben-Gurion University of the Negev, Israel
Pascal Schweitzer, TU Kaiserslautern, Germany
Petr Golovach (co-chair), University of Bergen, Norway
Sebastian Siebertz, University of Bremen, Germany
Saket Saurabh, Indian Institute of Mathematical Sciences, India, and University of Bergen, Norway
Tillmann Miltzow, Utrecht University, Netherlands
Vincent Cohen-Addad, Google Zurich, Switzerland
William Lochet, University of Bergen, Norway


FRONTIERS OF PARAMETERIZED COMPLEXITY online talk series about latest in the field. All are welcome to attend these online talks and interact with the speaker and other attendees remotely via Zoom.

THIS WEEKS TALK

*Date and Time: May 27, 2021 at 17:00 hours Bergen time (GMT+2)
*Speaker: Tuukka Korhonen <https://tuukkakorhonen.com/>
*University of Helsinki
*Title: Single-Exponential Time 2-Approximation Algorithm for Treewidth

*Abstract: We give an algorithm, which given an n-vertex graph G and an integer k, in time 2^O(k) n either outputs a tree decomposition of G of width at most 2k + 1 or determines that the treewidth of G is larger than k. The previous best approximation ratio in time 2^O(k) n was 5, and in time 2^O(k) n^O(1) was 3, both given by Bodlaender et al. [SICOMP '16]. Our algorithm is based on a proof of Bellenbaum and Diestel [Comb. Probab. Comput. '02]

Talks will be held every Thursday at 17:00 Bergen time (GMT+1). More information: https://frontpc.blogspot.com. To receive notifications of the talk announcements, please send an email at ed.gpm.fni-ipm|amrahsr#ed.gpm.fni-ipm|amrahsr with the subject 'Subscribe FrontPC' (Not needed if you are already subscribed to these notifications).

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.

List of previous talks (https://frontpc.blogspot.com/2020/) and their video recordings at our YouTube channel Frontiers of Paramerterized Complexity (https://www.youtube.com/channel/UCdfML-PShQNSCeqbz9Ol_oA).

For any further questions, please contact one of the following.
Roohani Sharma, Max Planck Institute for Informatics: ed.gpm.fni-ipm|amrahsr#ed.gpm.fni-ipm|amrahsr
Saket Saurabh, Institute of Mathematical Science, ni.ser.csmi|tekas#ni.ser.csmi|tekas
Fedor Fomin, University of Bergen, on.biu.ii|nimof#on.biu.ii|nimof


FPT YOUTUBE CHANNEL.

Subscribe to Youtube "FPT Complexity".
Jungho Ahn has agreed to create and administrate the channel.
Please send your playlists and suggestions and contact Jungho if you would like to join as an admin.
<rk.ca.tsiak|nhaohgnuj#rk.ca.tsiak|nhaohgnuj>.


The Fifth Workshop on Local Algorithms (WOLA 2021)
June 14-15, 2021. Virtual event.
https://www.local-algorithms.com <https://www.local-algorithms.com>
Participation is FREE, but please register by June 10th.

Local algorithms; that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of the related areas include sublinear-time algorithms, distributed algorithms, streaming algorithms, (massively) parallel algorithms, inference in large networks, and graphical models. These communities have similar goals but a variety of approaches, techniques, and methods. This workshop is aimed at fostering dialogue and cross-pollination of ideas between the various communities.

This year, the workshop will include A poster session, Invited long talks, An "Ask Me Anything" session:Moderated by Merav Parter, Junior-senior social meetings, A slack channel, Open problem session:More details soon to come.

Join the WOLA mailing list
For any questions related to WOLA 2021, please do not hesitate to send an email to moc.liamg|srezinagro.alow#moc.liamg|srezinagro.alow <mailto:wola.organizers@gmail.com>.

Invited Speakers

James Aspnes (Yale)
Jelani Nelson (Berkeley)
Elaine Shi (Cornell)
Christian Sohler (University of Cologne)
Uri Stemmer (Ben-Gurion University)
Mary Wootters (Stanford)


ICALP requests help. ICALP 2021 is offering a student volunteer programme which offers free registration in exchange for technical assistance with running the sessions. Please check http://easyconferences.eu/icalp2021/registration/ for details.

The main duties of a student volunteer:
- To provide support in technical sessions, either for the main conference or workshops or both. This mainly consists of helping presenters to work with the online conference platform. Training will be given.
- To help with social sessions, in as-yet-unspecified ways - for example, helping to assign people to groups, or technical troubleshooting.
- To answer queries from conference participants, passing such queries to members of the organising committee if necessary.

The dates when you will be needed are as follows:
- Morning of the 1st and afternoon of the 2nd July for conference rehearsal and training.
- Tuesday 13th to Friday 16th July inclusive for the main conference - though you will only be asked to volunteer over two of these days. We will do our best to accommodate preferences in our scheduling.

If you are interested in volunteering, please see the draft job description, and email Dr Jess Enright (mailto:jessica.enright@glasgow.ac.uk) to register your interest, including "ICALP Student Volunteer" in the subject line.

Applications are open until sufficient volunteers are recruited, or until June 18th at the latest. You should be notified of the outcome of your application within 5 business days of your application.


The 15th Frontiers of Algorithmics Workshop (FAW 2021) will be held as a track in IJTCS 2021.

The deadline of submission is extended to 26 May, 2021.

Webpage: https://econcs.pku.edu.cn/ijtcs2021/CFP_G.htm

Submission: May 26, 2021, 11:59 pm anywhere on Earth, Notification: June 26th, 2021

IJTCS 2021 is an International Joint Conference on Theoretical Computer Science to be held on August 16-20, 2021, cooperated with Peking University in Beijing. And IJTCS2021 is just the second time IJTCS. IJTCS 2021 will cooperate with CSIAM and CCF to provide you with a feast of theoretical computer science.

This meeting welcomes author submission of papers concerning any branch of the theoretical computer science, together with focus tracks in Algorithmic Game Theory, Blockchain, Multi-agent Reinforcement Learning, Quantum Computation, Theory of Machine Learning, Machine Learning, and Formal Method, and Algorithm and Complexity. We will also host a Female Scientist Forum, a Young PhD Forum, and an Undergraduate Research Forum.

The following tracks are open to submission this year:

Track A: Algorithmic Game Theory
Track B: Game Theory in Blockchain
Track G: The 15th Frontiers of Algorithmics Workshop

For track specific requirements, please check: https://econcs.pku.edu.cn/ijtcs2021/Call_for_Papers.htm

Conference Chair: John E.Hopcroft (Cornell University), Huimin Lin (UCAS)

General Chair: Xiaotie Deng (Peking University)


23rd International Symposium on Fundamentals of Computation Theory (FCT 2021)
September 12-15, 2021, Athens, Greece
https://www.corelab.ntua.gr/fct2021
Submission deadline: May 9, 2021 (abstracts) / May 16, 2021 (full papers)

FCT was established in 1977 as a forum for researchers interested in all aspects of theoretical computer science, and in particular algorithms, complexity, formal and logical methods. FCT 2021 will be hosted by the National Technical University of Athens partially or completely online, depending on the status of the COVID-19 pandemic.

Important Dates
Abstract registration: May 9, 2021 (AoE)
Full paper submission: May 16, 2021 (AoE)
Symposium: September 12-15, 2021

The program committee is soliciting original and significant research contributions to the fundamentals of computation theory, including (but not limited to):

Algorithms: algorithm design and optimization / data structures/ combinatorics and analysis of algorithms/ randomized algorithms/ approximation algorithms/ parameterized and exact algorithms computational algebra and number theory/ computational geometry/ parallel algorithms/ distributed algorithms and protocols/ online algorithms/ streaming algorithms/ algorithmic game theory/ computational foundations of machine learning/ computational biology

Complexity: models of computation/ computational complexity/ / Boolean/algebraic circuits and functions/ randomized / derandomization/ interactive proofs/ computational foundations of cryptography/ quantum computation/ complexity theory/ lower bounds/ counting complexity

Formal methods: algebraic and categorical methods/ automata and formal languages/ database theory/ foundations of concurrency and distributed systems/ logic and model checking/ models of reactive, hybrid, and stochastic systems/ principles of programming languages/ program analysis and transformation/ security/ specification, refinement, and verification/ type systems/ ad hoc, dynamic, and evolving systems/ foundations of cloud computing and ubiquitous systems

Invited Speakers
Constantinos Daskalakis, Massachusetts Institute of Technology
Daniel Marx, Max Planck Institute for Informatics
Claire Mathieu, CNRS and University of Paris
Nobuko Yoshida, Imperial College London


The 7th International Conference on Algorithmic Decision Theory - ADT 2021 will take place at the Institute de Recherche en Informatique de Toulouse (IRIT) and University of Toulouse 1 Capitole from November 3 - 5, 2021, Toulouse, France

See: https://www.irit.fr/ADT2021

The ADT 2021 conference focus is on algorithmic decision theory broadly defined, seeking to bring together researchers and practitioners coming from diverse areas of Computer Science, Economics and Operations Research in order to improve the theory and practice of modern decision support. The conference topics include research in Algorithms, Argumentation Theory, Artificial Intelligence, Computational Social Choice, Database Systems, Decision Analysis, Discrete Mathematics, Game Theory, Machine Learning and Adversarial Machine Learning, Matching, Multi-agent Systems, Multiple Criteria Decision Aiding, Networks, Optimization, Preference Modelling, Risk Analysis and Adversarial Risk Analysis, and Utility Theory.

ADT 2021 provides a multi-disciplinary forum for sharing knowledge in this area with a special focus on algorithmic issues in Decision Theory, continuing the tradition of the first six editions of the International Conference on Algorithmic Decision Theory (ADT 2009 Venice, ADT 2011 Rutgers, ADT 2013 Brussels, ADT 2015 Lexington, ADT 2017 Luxembourg, ADT 2019 Durham NC) which brought together researchers and practitioners from diverse areas of computer science, economics, and operations research from around the globe.

Title and abstract submission: April 30, 2021 (AoE), Full paper submission: May 7, 2021 (AoE)

INVITED SPEAKERS
Edith Elkind, University of Oxford, UK
Christophe Labreuche, Thales Research & Technology, France
Gianbattista Biggio, University of Cagliari, Italy


Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), 2021.
Please check https://eventos.ufabc.edu.br/lagos2021/ for further details and information on how to register.

When: from 17 to 21 May 2021
What: a symposium devoted to Algorithms, Graphs and Optimization
Where: online, by Virtual Chair on the Gather platform: https://www.virtualchair.net/events/lagos-2021
LAGOS 2021 contains great technical sessions, invited talks, a minicourse, and a special session to celebrate our dearest
Yoshiko Wakabayashi's birthday. We also have a best paper award.

Deadline for early registration is May 3rd and for late registration is May 17th.

We greatly look forward to seeing you at LAGOS 2021!
With best regards, Carlos E. Ferreira, Orlando Lee, Flavio K. Miyazawa


HIGHLIGHTS 2021: 9th annual conference on Highlights of LOGIC, GAMES, and AUTOMATA
15-17 September 2021, Aachen (but most probably online) http://highlights-conference.org

We invite submissions for contributed talks (around 10 minutes).

IMPORTANT DATES:
Submission deadline: 4 JUNE, 7pm GMT
Notification: 18 JUNE, 7pm GMT

Website: http://highlights-conference.org

HIGHLIGHTS 2021 is the 9th conference on Highlights of Logic, Games, and Automata that aims to integrate the diverse research community working in the areas of Logic, Finite Model Theory, Automata Theory, Games and Verification. Individual papers are dispersed across many conferences, which makes them challenging to follow. Participating in the annual
Highlights conference offers a wide picture of the latest research in the field and a chance to meet and interact with most of the members of the research community. The speakers are encouraged to present their best recent work at Highlights, whether already published elsewhere or not.

There will be a tutorial day (14 September) and three days for the conference (15-17 September).
This year's edition will be most probably held online, with no registration fees.

TUTORIAL (September 14)
Christoph Haase
Michal Pilipczuk

KEYNOTES
Rajeev Alur
Balder ten Cate
Karoliina Lehtinen
Nutan Limaye
Joel Ouaknine


The 46th International Symposium on Mathematical Foundations of Computer Science MFCS
August 23-27, 2021, Tallinn, Estonia
https://compose.ioc.ee/mfcs/

CALL FOR PAPERS
The MFCS conference series has been organised since 1972. Traditionally, the conference moved between the Czech Republic, Slovakia, and Poland, while since 2013, the conference travels around Europe. In 2021, it will come to Tallinn, Estonia. MFCS is a high quality venue for original research in all branches of theoretical computer science.

IMPORTANT DATES
Abstract Deadline: Thursday, April 30, 2021 (AoE)
Submission Deadline: Monday, May 3, 2021 (AoE)
Notification: Monday, June 21, 2021
Conference: Monday August 23 to Friday August 27, 2021

SUBMISSION GUIDELINES
Papers should be submitted electronically through EasyChair at
https://easychair.org/conferences/?conf=mfcs2021


ABEL PRIZE IN TCS!!!!
This is our area!!! It means that the relatively new field of Theoretical Computer Science (TCS) is fully recognized. This is what we do - algorithms and complexity. Congratulations to Avi Wigderson and László Lovász.

https://www.abelprize.no/artikkel/vis.html?tid=76403

After the two announcers, the 3-color problem is used to describe P vs NP and also randomness in cryptology.

The very last speaker, winner Avi W., talks about uses of TCS. Nice summary of applications. Very short.

Great news for our field!


Older news entries have moved to this page.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License