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. The FPT Newsletter needs a Chief Editor. Contact Fran Rosamond if interested.
Welcome to Abstract Methods in Multivariate Algorithmics (AMMA), a new international workshop bringing together two mathematical communities: (1) researchers in parameterized (multivariate) complexity theory and (2) researchers in applied topology and category theory.
WEBSITE: https://gataslab.org/amma
DATE: 12-16 August 2024
LOCATION: University of Florida (Gainsville, Florida, USA)
Abstract submission is now open. There will be post-proceedings.
The two communities share many core goals such as understanding compositional systems and compositional algorithms and the systematic confinement of emergent complexity (such as combinatorial explosion). The workshop will consist of a blend of invited and contributed talks as well as tutorials on parameterized complexity and applied category theory aiming to bridge the mathematical and linguistic gap between the two communities.
The topics may include but are not limited to:
• Sheaves and dynamic programming
• Well-quasi-ordering and encountered-instance algorithmic frameworks beyond worst-case analysis
• Universal obstructions in graph structural width metrics and a general theory of such metrics
• Abstract approaches to second-order Myhill-Nerode congruences and beyond
• Diagram-completion paradigms in parameterized complexity such as solution diversity,
• Transfer learning and dynamic input
• General theories of purposeful kernelization
• Parameterizing on quantization
• Inductive gradients in parameterized algorithms
• Problem-specific well quasi-ordering and functorial approaches to parameterized complexity classification
• Abstract views of input normal forms such as graphs as lineal topologies
• Abstract models of computation appropriate to truly linear FPT (O(n) + f(k)) algorithmics
• Abstract models of graphs arising from data points plus metric knobs, and their natural decompositions.
If you have any questions, feel free to contact any member of the organising committee:
— Benjamin Merlin Bumpus (moc.liamg|supmub.nilrem.nimajneb#moc.liamg|supmub.nilrem.nimajneb)
— Michael R. Fellows (on.biu|swollef.leahciM#on.biu|swollef.leahciM)
— Frances A. Rosamond (moc.liamg|4dnomasor.secnarf#moc.liamg|4dnomasor.secnarf)
— James P. Fairbanks (ude.lfu|jsknabriaf#ude.lfu|jsknabriaf)
We look forward to seeing you at AMMA 2024.
Association for Computing Machinery
@TheOfficialACM
🏆We're thrilled to announce the recipient of the 2023 #ACMTuringAward: Avi Wigderson.
Wigderson is recognized for his foundational contributions to the theory of computation. Join us in celebrating his incredible achievements! Learn more here: https://bit.ly/4aGpbiM @the_IAS
Congratulations to Jiehua Chen who has been promoted to tenured Associate Professor with the Algorithms and Complexity group at TU Wie. Her research interests include the parameterized complexity of, and the design and analysis for, combinatorial problems arising in contexts such as optimization problems related to graphs and hypergraphs and Computational Social Choice (computational problems around voting, domain restrictions, and preference-based stable matching problems). She is offering a PhD position for her WWTF research project titled "Structural and Algorithmic Aspects of Preference-based Problems in Social Choice."
Congratulations to Neena Gupta, Indian Statistical Institute (ISI) in Kolkata one of the most promising young mathematicians working in India today, has been selected to deliver the Emmy Noether Lecture at the Joint Mathematics Meetings to be held in Seattle, US, in January 2025. This is a big deal, not only because it is a high-profile academic event, but also because Noether was a pioneering mathematician who fled Nazi Germany in 1933 and spent the next two decades in the US advancing the field of abstract algebra and forging a path for future women mathematicians. “For Indian women, it is very important to get recognised, because otherwise, their families may no longer support them in their pursuit of research,” Gupta says. Pure luck and a rebellious streak combined to help her pursue a Master’s programme in mathematics followed by a PhD. “ISI was just a kilometre from home. That’s the only reason my parents allowed me to study further. There was talk of marriage when I finished my undergrad but I asked for more time. I promised my parents I would finish my PhD in two-three years,” says Gupta, who now has an eight-year-old daughter.
Gupta won the 2021 Ramanujan Prize for young mathematicians from developing countries for her work in affine algebraic geometry and commutative algebra, specifically for her solution to the Zariski cancellation problem. “International recognition like this comes maybe once in a lifetime if one is lucky. I am very aware that this award may well inspire other young Indian women to take up mathematics,” says Gupta, who was awarded the Shanti Swarup Bhatnagar prize, the highest honour in India in the field of science and technology, in 2019. Slowly, as more women take up research in mathematics—Gupta has two women students pursuing their PhD with her guidance—she hopes it becomes a level playing field. “Academics get maternity leave but only if they have tenured positions. What if you are a postdoc?” Women have to “make sure to showcase their work” and “put themselves out there” to be recognised, she says. “When you have a young child, you tend not to travel to conferences or network with other faculty members. I have been in that position and I know how important it is to sell yourself, even as you continue to do good maths. It’s definitely harder for women. But when maths is a passion, not just a job, you don’t worry about all this, you don’t even worry that it may not be a lucrative career. You just want to keep doing maths.” https://openthemagazine.com/cover-stories/strength-in-numbers/
CONGRATULATIONS TO ALL THE GREAT PAPERS IN CONFERENCES! Please add your papers to the wiki. We like to know. We like to recognize your work. Here are some papers from STOC24.
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidt
h Tuukka Korhonen (University of Bergen); Marek Sokolowski (University of Warsaw).
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Venkatesan Guruswami (University of California, Berkeley); Bingkai Lin (Nanjing University); Xuandi Ren (University of California, Berkeley); Yican Sun (Peking University); Kewen Wu (University of California, Berkeley).
The Asymptotic Rank Conjecture and the Set Cover Conjecture are not Both True
Andreas Björklund (IT University of Copenhagen); Petteri Kaski (Aalto University).
Counting Small Induced Subgraphs with Edge-monotone Properties
Simon Döring (Max Planck Institute for Informatics; Saarbrücken Graduate School of Computer Science; Saarland Informatics Campus); Dániel Marx (CISPA Helmholtz Center for Information Security); Philip Wellnitz (Max Planck Institute for Informatics; Saarland Informatics Campus).
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland (University of California at Santa Barbara); Daniel Lokshtanov (University of California Santa Barbara, USA); Tomáš Masarík, Marcin Pilipczuk, Michal Pilipczuk (University of Warsaw); Pawel Rzazewski (Warsaw University of Technology).
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
V. Arvind (Institute of Mathematical Sciences (HBNI), Chennai Mathematical Institute, India); Abhranil Chatterjee (Indian Statistical Institute, Kolkata, India); Partha Mukhopadhyay (Chennai Mathematical Institute, India).
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland (University of California at Santa Barbara); Daniel Lokshtanov (University of California Santa Barbara, USA); Tomáš Masarík, Marcin Pilipczuk, Michal Pilipczuk (University of Warsaw); Pawel Rzazewski (Warsaw University of Technology).
Combinatorial Characterizations of Monadically NIP Graph Classes
Jan Dreier (TU Wien); Nikolas Mählmann (University of Bremen); Szymon Torunczyk (University of Warsaw)
CONGRATULATIONS to ALL THE PACE AWARD WINNERS. This year, PACE held a hugely successful PACE POSTER SESSION. Some viewers stayed on and on until after dinner with their notebooks and computers out, quizing and discussing with the poster presenters.
CONGRATULATIONS 2023 ALGO-IPEC NERODE PRIZE WINNERS
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk for their paper: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.
The talk was given by Michal and Johan. The program chair is Magnus Wahlström.
The audience for the Nerode Prize talk overflowed the room and a second room showed the talk on video. Also, many ESA papers were about Parameterized Complexity. Lots of wonderful new ideas being shared here.
CONGRATULATIONS to Yosuke Mizutani (Univ Utah) who is the inaugural winner of the new PACE THEORY AWARD awarded at the 2023 ALGO-IPEC PACE MEETING, Amsterdam. Yosuke is finishing his PhD. and would be interested in a position in Europe.😁
CONGRATULATIONS to Yosuke, student of Prof. Blair D. Sullivan. The prize is being awarded by Sebastian Berndt (Univ Luebeck) and Max Bannach, the 2023 PACE Chairs.
--
ROLF NIEDERMEIER — SPECIAL ISSUE OF JCSS.
Rolf Niedermeier was one of the pioneers of parameterized algorithms, a tireless supporter of the computer science community, and a great friend. To commemorate his life and his extensive and fruitful body of work, the Journal of Computer and System Sciences, where Rolf Niedermeier also served as associate editor, will publish a special issue.
The issue will feature research articles that are concerned with the topics in computer science to which Rolf Niedermeier contributed. We thus invite high-quality submissions reporting on original research in these areas.
Relevant topics are, for example:
- Parameterized complexity,
- Fixed-parameter algorithms,
- Kernelization,
- Graph algorithms,
- Computational social choice,
- Computational biology,
- String algorithms,
- Temporal graphs, and
- Algorithm engineering for hard problems.
A contribution may include a section describing Rolf's influence on the authors, both on their academic careers and personal lives.
The submissions will be peer-reviewed according to the high standards of Journal of Computer and System Sciences.
Submission deadline: July 31 2023
Submission portal: https://www.editorialmanager.com/jcss/default2.aspx
Make sure to select VSI:Rolf Niedermeier [MGE - Saket Saurabh] at the “Article Type” step in the submission process.
Best regards,
Fedor Fomin, Saket Saurabh, and Christian Komusiewicz
PROFESSORS, SUBMIT YOUR STUDENT'S THESIS FOR THE Algorithms 2023 Best Ph.D. Thesis Award.
The journal "Algorithms" (https://www.mdpi.com/journal/algorithms) wants to encourage and motivate Ph.D. students
or recently qualified Ph.D. awardees in the field of algorithms. Applications can be submitted online at https://www.mdpi.com/journal/algorithms/awards/submit/2240 by 28 February 2024.
The prizes consist of:
– A bonus (CHF 500);
– A certificate;
– The offer to publish one paper free of charge in Algorithms after peer review before the end of 2024.
More details about the award and application requirements can be found at: https://www.mdpi.com/journal/algorithms/awards/2240
We would appreciate you spreading this news among your research community, and we welcome and encourage Ph.D. students from your research group to submit applications.
EPIT 2023: The Kaleidoscope of Complexity Theory. PhD and Post-Docs sign up. Registration closes on May 8.
50th École de Printemps d'Informatique Théorique
12-16 June, Île d'Oléron, France https://epit2023.sciencesconf.org
The Kaleidoscope of Complexity Theory will take place at the Vieille Perrotine CAES/CNRS holiday center on Oléron
Island (on the Atlantic coast of France), from Monday June 12 to Friday June 16, 2023.
EPIT is intended for PhD students as well as established researchers who wish to learn more about neighboring areas.
PROGRAM
The school will consist of 6 courses, on the following topics:
1. Descriptive Complexity: Albert Atserias, Universitat Politècnica de Catalunya
2. Randomness: Valentine Kabanets, Simon Fraser University
3. Lower Bounds: Paul Beame, University of Washington
4. Hardness of Approximation:
Irit Dinur, Weizmann Institute
5. Fine-Grained and Parameterized Complexity:
Michał Pilipczuk, University of Warsaw
6. Algebraic and Geometric Complexity
Guillaume Malod, Université Paris Cité, and
Christian Ikenmeyer, University of Warwick
ORGANIZATION
Damiano Mazza, CNRS, Université Sorbonne Paris Nord
Joanna Ochremiak, CNRS, Université de Bordeaux & University of Warsaw
Sylvain Perifel, Université Paris Cité
Thomas Seiller, CNRS, Université Sorbonne Paris Nord
Adjoint Homomorphism Counting Workshop (ad hoc), Adjoint with ICALP 2023: Announcement and Call for Contributed Talks
July 10, 2023
Paderborn, Germany
Website: https://sites.google.com/view/adhocworkshop
In recent years, the study of homomorphism counts resurged in complexity theory, database theory and network sciences, since homomorphism counts turned out to be fundamental in understanding the complexity of counting small patterns. From a mathematical perspective, homomorphism counts encode valuable information, specify structures up to isomorphism, and capture the expressivity of important fragments of logic. Moreover, they enable a definition of convergent graph sequences that leads to so-called graph limits.
The ad hoc workshop, held in person in Paderborn, just before ICALP 2023, will (i) provide a forum for researchers who already work on homomorphism counts, and (ii) invite scientists from other areas to this fascinating subject through several survey talks.
Organizers:
- Radu Curticapean, IT University of Copenhagen
- Marc Roth, University of Oxford
CONGRATULATIONS Neil Koblitz, co-recipient of the Levchin Prize and the Eduard Rhein Stiftung Technology Award.
Neil along with Victor Miller, shares the Levchin prize 2021 and the Eduard Rhein Stiftung Technology Award for 2020. Koblitz will be in Germany soon to receive the prize! He will give a talk in Munich. The Levchin prize honors major innovations in cryptography that have had a significant impact on the practice of cryptography and its use in real-world systems. Koblitz and Miller are being honored for their independent developments of elliptic curve cryptography (ECC), the idea to use the group of points on an elliptic curve defined over a finite field in discrete log cryptosystem.
Neil is with Mike Fellows the developer of the Kid Krypto system, which has spurred adult Polly Cracker crypto and Grobner Basis Cryptosystems. See the Kid Krypto on Neil's website and Crypto Galore! Koblitz, N. (2012). Crypto Galore!. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds) The Multivariate Algorithmic Revolution and Beyond. Lecture Notes in Computer Science, vol 7370. Springer, 39-50.. ude.notgnihsaw.htam|ztilbok#ude.notgnihsaw.htam|ztilbok
EATCS-IPEC Nerode Prize - Final Call for Nominations Deadline: 15 April, 2023
The EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics, is presented annually with the presentation taking place at IPEC (International Symposium on Parameterized and Exact Computation). IPEC 2023 is due to take place as part of ALGO 2023 on 4-8 September in Amsterdam, the Netherlands. The Prize is named in honor of Anil Nerode in recognition of his major contributions to mathematical logic, theory of automata, computability, and complexity theory.
AWARD COMMITTEE. The winning paper(s) will be selected by the EATCS-IPEC Nerode Prize Award Committee.
Fedor Fomin, chair (University of Bergen, on.biu|nimof.rodef#on.biu|nimof.rodef<mailto:fedor.fomin@uib.no>)
Thore Husfeldt (IT University of Copenhagen, kd.uti|eroht#kd.uti|eroht<mailto:thore@itu.dk>)
Sang-il Oum (IBS and KAIST, rk.er.sbi|lignas#rk.er.sbi|lignas<mailto:sangil@ibs.re.kr>)
Deadline for Nominations: 15 April, 2023.
Decision: 15 June, 2023.
Award presentation at IPEC.
You are cordially invited to attend FPT Fest in the honour of Mike Fellows.
June 12 to June 16, 2023
++https://www.uib.no/en/rg/algo/160260/fpt-fest-2023-honour-mike-fellows
Wave picture is created by Felix Reidl.
PROGRAM
The symposium will consist of a number of invited talks, minisymposia, and one full day (Wednesday) devoted to Mike and his contributions to computer science.
MINI-SYMPOSIA
Topic Organizer
Treewidth Dimitrios M. Thilikos
Flow augmentation & cuts Magnus Wahlström
Twinwidth Eun Jung Kim
Graph isomorphism Daniel Neuen
Social choice & matching Jiehua Chen
Scheduling Celine Swennenhuis
FPT in ML Robert Ganian
Structural parameterizations Ignasi Sau
Logic metatheorems Sebastian Siebertz
Exact algorithms Jesper Nederlof
Mathematical programming Martin Koutecký
Kernelization and beyond Bart M. P. Jansen
SAT and CSPs Stefan Szeider
Each mini-symposium lasts for 2 hours. Together with these mini-symposia, we have invited talks:
INVITED TALKS
Counting complexity Marc Roth
Treewidth Tuukka Korhonen
Parameterized complexity & Logic Szymon Toruńczyk
Flow augmentation Marcin Pilipczuk
History of FPT Dániel Marx
Parameterized Computational Geometry Meirav Zehavi
Mike Fellows (together with Rod Downey) is one of the principal founders of parameterized complexity, a two-dimensional framework for complexity analysis and algorithm design based on two fundamentally different kinds of timecosts: polynomial timecosts as a function of the overall input size (as in the central concept of P in the one-dimensional classical framework for computational complexity) together with a second dimension of timecosts associated to a vector of relevant secondary measurements, such as input structure, degree of approximation or amount of quantization, algorithmic operational aspects, etc., to confine the explosions.
Besides his work in mathematics, algorithms and complexity theory, Mike is noted for his seminal contributions to the popular communication of the mathematical sciences and related efforts in Computer Science curriculum reform at all age levels, including the much-translated "Computer Science Unplugged" (with New Zealand coauthors Tim Bell and Ian Witten), which has had substantial world-wide impact.
For these two contributions, Mike received Australia's highest civilian honor, Order of Australia, Companion to the Queen (AC), an honor descended from and essentially equivalent to a UK Knighthood. He is also only the second Norwegian to be listed on New Zealand's remarkable Hobbit List (technically: HonFRSNZ), the first being G.O. Sars, one of the world's first Oceanographers, who notably wrote a book about the freshwater crustaceans of New Zealand, thus joining north and south in the early days of Science.
REGISTRATION
Please go to the registration form to register your attendance (https://skjemaker.app.uib.no/view.php?id=14553940). The symposium will happen in Grand Hotel Terminus, Bergen.
ORGANIZING COMMITTEE. The program is still being finalized.
This symposium is organized by Saket Saurabh, Fedor V. Fomin, Bart M. P. Jansen, Marcin Pilipczuk, Michał Pilipczuk, Daniel Lokshtanov,Pål Grønås Drange
+ CONGRATULATIONS! NEW FAMILY MEMBER. Welcome Baby Timoteus Koutecký Baby Tim is keeping his father Martin busy. Martin is also working on his latest research grant: Efficient and Realistic Models for Computational Social Choice, 2022 present. Grant 22-22997S of the Czech Science Foundation ((GACR). Principal investigator Martin Koutecký. Team member Pavel Vesely. Computer Science Institute of Charles University.
CONGRATULATIONS! Prof. Dr. Christian Komusiewicz.
Christian is now Chair of the Algorithms Research Group in Jena. He has left the University of Marburg and he is now at Friedrich-Schiller-Universität Jena. Christian's new homepage can be found at: https://www.fmi.uni-jena.de/algo
CONGRATULATIONS!
Professor Celina de Figueiredo has beeen elected a member of the Brazilian Academy of Sciences.
Celina is Professor in the Department of Computer Science, Programa de Engenharia de Sistemas e Computação, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil.
CONGRATULATIONS!
Arne Meier (Leibniz University of Hannover) has been awarded a three-year DFG project "Database Repairs: New Bridges to Logics“ for about €300k. In this project, different concepts from database theory (Repair Checking, Conjunctive Query Answering, EMVDs) as well as data exchange problems and argumentation formalisms will be studied from the perspective of Dependence Logic within the framework of parameterized complexity.
SUMMER SCHOOL IN GAME THEORY AND SOCIAL CHOICE
The objective of the summer school is to provide fundamental knowledge in game theory and social choice to researchers or research students who may find the topics useful in their own research or senior undergraduate students who are looking for potential research directions.
At the same time, the students will also have the opportunity to learn about the state of the art in these fields via keynote talks.
The summer school is organized by Department of Computer Science, City University of Hong Kong via zoom during June 20 - June 24 , 2022. The intended participants of the summer school are students within computer science, or students with mathematics or economics background interested in game theory and social choice.
Below are the speakers for the summer school this year. For more details on the summer school and the registration, please refer to the website of the summer school: https://www.cs.cityu.edu.hk/~gtsc/
Keynote Speaker List:
Kurt Mehlhorn, Max-Planck-Institut
Herve Moulin, University of Glasgow
Shanghua Teng, University of Southern California
Contact: Minming LI <kh.ude.uytic|il.gnimnim#kh.ude.uytic|il.gnimnim>
Subscribe to the mailing list:ude.ekud|cosmoc#ude.ekud|cosmoc
The 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) invites papers presenting original research in the area of parameterized and exact algorithms and complexity.
TIME&PLACE: September 7-9, 2022 in Potsdam, Germany (co-located with ALGO/ESA).
TOPICS:
The topics include but are 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;
- engineering and experimentation of exact, parameterized, and kernelization algorithms.
The full paper submission deadline is June 24, 2022 (23:59 AoE). Note that this year IPEC employs a double-blind reviewing process. Further information is available at https://algo2022.eu/ipec/.
MEMORIAL FOR ROLF IS 30.04.2022
Rolf's student have organized a memorial at TU Berlin. The details are: April 30, TU Berlin, for more information and to join, send a mail to ed.nilreb-ut.tka|lairomem#ed.nilreb-ut.tka|lairomem
We are deeply grieved by the death of our dear friend and colleague, Gerhard J. Woeginger, who died in April after a long illness. Gerhard was a professor at RWTH Aachen University, where he chaired the algorithms and complexity group in the department of computer science.
Gerhard was born in Graz, Austria in 1964. He obtained a diploma from the Graz University of Technology (TU Graz) in 1987, and completed his Ph.D. at TU Graz 1991 under the supervision of Franz Rendl. He worked on the faculty of TU Graz from 1991 to 2001, where he completed his habilitation in 1995. He then moved to the University of Twente from 2001 to 2004, to TU Eindhoven, from 2004 to 2016, and finally to RWTH Aachen in 2016.
He was program chair of the European Symposium on Algorithms in 1997, of the algorithms track of the International Colloquium on Automata, Languages and Programming in 2003, of the European Conference on Operational Research in 2009, and of several other conferences.
In 1996, Woeginger won the Start-Preis, the highest Austrian award for scientists under the age of 35. He won a Humboldt Research Award in 2011. In 2014, he was elected to the Academia Europaea.
IT IS WITH DEEP SADNESS AND SHOCK THAT WE REPORT THE DEATH
OF OUR DEAR FRIEND AND COLLEAGUE ROLF NIEDERMEIER.
The details are not yet clear, but Rolf went home feeling ill, and
later phoned his students saying he was feeling better.
This is a sad loss to all of us.
There will be a Memorial written by Rolf's students in the next FPT newsletter.
EATCS-IPEC Nerode Prize - Call for Nomination
Deadline for nominations: 15 May, 2022
Decision: 1 July, 2022.
The EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics presentation taking place at IPEC (International Symposium on Parameterized and Exact Computation). IPEC 2022 is due to take place as part of ALGO 2022 on 5-9 September in Potsdam, Germany. The Prize is named in honor of Anil Nerode in recognition of his major contributions to mathematical logic, theory of automata, computability and complexity theory.
The winning paper(s) will be selected by the EATCS-IPEC Nerode Prize Award Committee:
Anuj Dawar, chair (University of Cambridge, ku.ca.mac.lc|rawad.juna#ku.ca.mac.lc|rawad.juna)
Fedor Fomin (University of Bergen, on.biu|nimof.rodef#on.biu|nimof.rodef)
Thore Husfeldt (IT University of Copenhagen, kd.uti|eroht#kd.uti|eroht)
The Award Committee is solely responsible for the selection of the winner of the award which may be shared by more than one paper or series of papers. The Award Committee reserves the right to declare no winner at all.
Eligible is any research paper or series of research papers by a single author or by a team of authors published in a recognized refereed journal. The research work nominated for the award should be in the area of multivariate algorithms and complexity meant in a broad sense, and encompasses, but is not restricted to those areas covered by IPEC. The Award Committee has the ultimate authority to decide on the eligibility of a nomination. Papers authored by a member of the Award Committee are
not eligible for nomination.
Note that the past restrictions that require a certain number of years before/after the publication of the nominated papers have been removed.
Nominations may be made by any member of the scientific community including the members of the Award Committee. A nomination should contain a brief summary of the technical content of each nominated paper and a brief explanation of its significance. Nominations are done by an email to the Award Committee Chair with copies to the members of the committee. The Subject line of the nomination E-mail should contain the group of words "Nerode Prize Nomination".
PCCR-2022: 3RD WORKSHOP ON PARAMETERIZED COMPLEXITY OF COMPUTATIONAL REASONING
— co-located with FLoC/IJCAR 2022 — July 31 - August 1, 2022, Haifa, Israel
Web-site: https://algorithms.leeds.ac.uk/pccr2022/
Submission link: https://easychair.org/conferences/?conf=pccr2022
Submission deadline: May 10, 2022
Theme: Parameterized complexity of problems in Logic, AI, and ML.
This workshop aims to support a fruitful exchange of ideas between the research on parameterized complexity (PC) on one side and the research on problems in computational reasoning (Logic and probabilistic reasoning), Artificial Intelligence (AI), and Machine Learning (ML) on the other.
Topics of interest include but are not limited to:
- Parameterized complexity of problems in Logic, AI, Computational Social Choice, and ML.
- Recent developments in PC and the above areas plus introduction of new problems that might benefit from the PC approach.
- Various (structural) parameteriziations such as decompositions, backdoor sets, and hybrid parameterizations.
- Theory and practice of parameterized algorithms.
The workshop will feature invited and contributed talks with surveys and new technical results, an open problem session, and a panel discussion on future research directions. Apart from talks on parameterized complexity we are also interested in presentations that highlight structural parameters that have not been studied within the framework of parameterized complexity so far.
If you would like to give a talk at the workshop, please submit a short abstract of your talk via Easychair by the submission deadline in PDF format. The abstract and talk can be based on published or unpublished results, and we welcome overview and survey talks, besides regular technical talks. Contributed talks are expected to be around 30 minutes each.
- Green light physical conference: 1 May 2022
- Early registration starts: 1 May 2022
- Workshop paper submission deadline: 10 May 2022
- Workshop accepted paper notifications: 15 June 2022
ORGANIZATION
- Sebastian Ordyniak, University of Leeds, United Kingdom (moc.liamg|kainydros#moc.liamg|kainydros)
- M.S. Ramanujan, University of Warwick, United Kingdom (ku.ca.kciwraw|narahdirS-ihzupadaaM.R#ku.ca.kciwraw|narahdirS-ihzupadaaM.R)
- Ronald de Haan, University of Amsterdam, Netherlands (ue.naaheddlanor|em#ue.naaheddlanor|em)
AIROYoung during the next EURO Conference that will be held in Espoo (Finland) on July 3-6, 2022.
The title of our session is "Green Scheduling", given our attention to current and important issues such as the environment and sustainability. This theme can cover both routing (e.g., air line and public transportation) and energy (e.g., wind, power, EV), but not only. If you work on these topics or others related, join us and present your research!
We will give priority to young researchers (under 35 years old or at the first stages of the career)
You can submit your abstract by going to the submission page at https://www.euro-online.org/conf/euro32 and inserting the following invitation code: e554caa5.
- submission deadline: March 4, 2022.
We look forward to receiving your abstract! If you have any questions, do not hesitate and contact us at moc.liamg|srehcraeser.gnuoy.oria#moc.liamg|srehcraeser.gnuoy.oria<mailto:airo.young.researchers@gmail.com>.
Computer Science Logic (CSL) is the annual conference of the European Association for Computer Science Logic (EACSL), see https://www.eacsl.org/. CSL is an interdisciplinary conference, spanning across both basic and application oriented research in mathematical logic and computer science.
CSL'22 will be held on February 14 - 19, 2022, online, hosted by the University of Göttingen. website:
http://csl2022.uni-goettingen.de/
Accepted papers: The Program Committee selected 35 accepted papers for presentation at CSL 2022. Their titles and authors can be seen here: http://csl2022.uni-goettingen.de/#acceptedpaper
Registration: https://events.gwdg.de/event/95/
UNESCO World Logic Day on January 14th, 2022. Attend Moshe Vardi’s online talk.
Title: From Greek Paradoxes to Political Paradoxes
Abstract: The ancient Greeks invented logic, as a tool to discover eternal truths. They also invented paradoxes, as a tool to sharpen the mind. Famous Greek paradoxes are the Liar’s Paradox, Zeno’s Paradox, and the Sand-Heap Paradox. The Liar’s Paradox led, at the start of the 20th Century, to a foundational crisis of mathematics, which led to the development of computability theory in the 1930s, as well as the unresolvable mathematical conundrum of Gödel’s Incompleteness Theorem.
Computing technology, which also emerged in the 1930s, ultimately led, at the start of the 21 Century, to the emergence of social media. Today, our society is struggling with the adverse societal effects of social media. These adverse effects can also be understood in terms of the Greek paradoxes, as well as their political versions, known as the Popperian Paradoxes. In fact, one can say that the Greek myths of Prometheus and Pandora already told us that technology does not come without adverse consequences, which is why John von Neumann, one of the most prominent computing pioneers, asked in 1955, “Can we survive technology?”
Find here information on how to register for the talk https://logicday.vcla.at/vienna-logic-day-lecture/
Registration is free.
CONFERENCE - 17th INTERNATIONAL COMPUTER SCIENCE SYMPOSIUM IN RUSSIA (CSR 2022).
June 29–July 3, 2022 in St. Petersburg, Russia. This is an absolutely gorgeous time to visit St. Petersburg and enjoy white nights. The conference will feature a number of invited talks by outstanding researchers, including the opening
lecture by Umesh Vasirani. In 2022, CSR is an official satellite of the International Congress of Mathematicians (ICM), which will also happen in St. Petersburg, Russia on July 6-14. Registered participants of ICM2022 will get visa-free entry to Russia. CSR 2022 will be held in a hybrid format: all authors who are unable to travel to Russia will be able to present their papers and participate remotely. The conference covers a wide range of topics in theoretical computer science and related fields:
https://logic.pdmi.ras.ru/csr2022/
The submission deadline has been extended to January 22, 2022 because of the current COVID-19 surge.
--
CONGRATULATIONS TO JAN ARNE TELLE (Univ. Bergen) Algorithms Group, who will lead the project “Machine Teaching for Explainable AI”. The Research Council of Norway has decided to support the project with 10 million NOK through their Enabling technologies program. The project involves the companies Equinor and BKK AS and also includes Pekka Parviainen in the UiB Machine Learning Group.
The project aims to develop methods to explain decisions based on use of Artificial Intelligence (AI) methods making the reasoning performed within the AI method understandable for a human. The companies involved are increasingly using AI methods in their operations and are eager to engage in the project since they see a need to better integrate AI methods in their operations.
NEW COURSE IN PARAMETERIZED COMPLEXITY ONLINE.
Saket and Neeldhara are offering an entry-level course on Parameterized Algorithms on one of India's largest MOOC platforms:
https://nptel.ac.in/courses/106/106/106106230/
Here is a short introduction for prospective students: https://www.youtube.com/watch?v=9x9pAn5DkZI
The course link above gives videos corresponding to the lectures. Well done, Neeldhara and Saket!
CONGRATULATIONS TO SAKET SAURABH(Univ. Bergen and Institute of Mathematical Sciences Chennai) for winning India's highly prestigious Shanti Swarup Bhatnagar Prize in Science and Technology. Saket has made fundamental contributions to the area of Parameterized Complexity and for leading the field by initiating new research directions to the community. This is easily among the highest honors for scientific achievement in India
CONGRATULATIONS TO THE 2021 NERODE PRIZE WINNERS
The EATCS-IPEC Nerode Award Committee has selected the paper as the recipient of the EATCS-IPEC Nerode Prize 2021: "Deciding Parity Games in Quasi-polynomial Time" by Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan. SIAM Journal of Computing, Special Issue dedicated to STOC 2017, pp. 152-188, 2020. The deep techniques in this paper inspired a long series of further improvements on the complexity of Parity Games and related problems. The paper is a true gem in multivariate algorithmic game theory.
From left to right: Professors Sanjay Jain, Frank Stephan and Wei Li from the NUS Department of Mathematics, Professors Cristian Calude from the University of Auckland, and Bakhadyr Khoussainov from the University of Electronic Science and Technology of China and the University of Auckland, winners of the EATCS-IPEC Nerode Prize.
BEST WISHES to R. Ramanujam (Jam), who has retired from IMSc. June 30th was his last day at IMSc after his glorious time at IMSc for over 30 years. Jam has considered everyone in the world as friend and colleague. He has been fully committed to sharing research and mathematics at all levels with children, taxi drivers, cleaning ladies, and all of us. Jam, we wish you continued joy in life with your family and many friends, music, and all your activities. See the website https://india.acm.org/education/learning/esp/r-ramanujam for a few details of Jam's extraordinary contributions.
CONGRATULATIONS Neeldhara Misra (IIT Gandhinagar), who has been selected as an Associate of the Indian Academy of Sciences. The Indian Academy of Sciences is considered among the most prestigious institutions of the country actively working in promoting progress and upholding the cause of science. Every year, the Academy selects a certain number of young scientists of great promise as Associates. Prof Neeldhara Misra is one of the eleven Associates selected from all over the country in 2021. Professor Misra's research focuses on the design and analysis of algorithms, computational social choice, extremal combinatorics, combinatorial game theory, combinatorial and computational geometry, and satisfiability and constraint satisfaction.
CONGRATULATIONS Aline Parreau (LIRIS -Université Claude Bernard Lyon 1).
Aline has received a French National Research Agency (ANR) Young Researcher (JCJC) award for the project, Positional Games: complexity, Algorithms and StrategiEs (PGASE). The award is for EUR 169k for 4 years. The project P-GASE is about the study of positional games, which are are 2-player turn-based, perfect information games played on a hypergraph H. Both players alternately claim vertices of H with the ultimate goal that the same player claims all the vertices of a hyperedge or prevents the other player from doing so. The popular game of Tic-Tac-Toe belongs to this class. The project will investigate combinatorial and parameterized complexity questions in regards to various positional games. The project is led by Aline Parreau who is a CNRS researcher at LIRIS, Université Lyon 1 and also involves 4 other faculty members: Eric Duchêne and Théo Pierron also from LIRIS, Valia Mitsou, IRIF, Université de Paris and Nicolas Nisse, Inria Sophia Antipolis. There will be postdoc openings, contact the PI.
CONGRATULATIONS Florent Foucaud (Université Clermont Auvergne). Florent has received a French National Research Agency (ANR) Young Researcher (JCJC) award for the project, Algorithmics for Metric Covering problems in Graphs (GRALMECO), with budget of EUR 169k for 4 years and includes funding for postdoc. it involves Caroline Brosse, Dipayan Chakraborty, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor and Jean-Florent Raymond from the LIMOS in Clermont-Ferrand, France (alphabetic order; the two first are PhD students, the others are faculty). The project website is perso.limos.fr/foucaud/GRALMECO. The project will study the algorithmic complexity of metric-based covering problems in graphs, viewed as networks with their underlying distance-metric. Examples of such problems are Metric Dimension, Geodetic Set, variants of Path Cover, distance-constrained Domination or Packing, etc. Such problems have important applications, such as routing or monitoring in communication and transportation networks, information retrieval in graph databases, or computational learning in large datasets.
CONGRATULATIONS Michael Lampis (LAMSADE - Université Paris-Dauphine).
Michael has received a French National Research Agency (ANR) Young Researcher (JCJC) award for the project, Sub-EXponential APproximation and ParamEterized ALgorithms (S-EXAP- PE-AL). The project is funded at EUR 177k and will run for 4 years, starting from early 2022. The topic of the project is the combination of modern techniques from parameterized complexity and exact algorithms, especially structural parameters related to graph widths, with ideas from approximation algorithms. Headed by Michael Lampis, included are Florian Sikora and Eunjung Kim (also from LAMSADE), Valia Mitsou (IRIF - Université de Paris) and Andreas-Emil Feldmann (Charles University).
CONGRATULATIONS Mateus de Oliveira Oliveira (Univ Bergen). Mateus's project Symbolic Algorithms: A Parameterized Approach (SYMBOALGO) will be funded by the Research Council of Norway (RCN) within the ground-breaking research initiative. About 190 projects were selected from a pool of 1600 applications. The budget of the project is NOK 13 Million
(approx EUR 1.3 Million), where NOK 12 Million will be financed by the RCN. The goal is to address important challenges in the Field of Artificial Intelligence using the framework of symbolic algorithms. The project will be carried out at the University of Bergen between the years 2021 and 2025 and includes funding for postdocs and students.
CONGRATULATIONS Édouard Bonnet (ENS Lyon). Édouard has received a French National Research Agency (ANR) Young Researcher (JCJC) award for the project, Twin-width: theory and applications (TWIN-WIDTH). The main open question that the project wishes to address is finding an FPT approximation for twin-width (outputting contraction sequences).
Participants in the project include Dibyayan Chakraborty (postdoc), Hugues Déprés (PhD student), Louis Esperet (G-SCOP, Grenoble), Colin Geniet (PhD student), Ugo Giocanti (PhD student, G-SCOP, Grenoble), Eunjung Kim (LAMSADE, Paris-Dauphine University), Stéphan Thomassé, and Rémi Watrigant. The funding of EUR 154k for 4 years covers two years of postdoc.
Édouard will give an Invited Tutorial on Twin Width at IPEC 2021.
CONGRATULATIONS M. S. Ramanujam (MSR) (Univ Warwick). MSR jointly with Graham Cormode
has been awarded an EPSRC Standard Research Grant, New Horizons in Multivariate Preprocessing (MULTIPROCESS). The 540K pound project will run for four years and has postdoc positions associated with it. The aim is to advance the mathematical theory of preprocessing by delivering and studying new formulations of effcient preprocessing that build on the notion of approximate kernelization and extend their scope to high-impact big data paradigms such as streaming algorithms.
CONGRATULATIONS to Vít Jelínek, Michal Opler, Jakub Pekárek (Charles University, Prague) who have been awarded the IPEC 2021 Student Best Paper Award for their paper, Long Paths make Pattern-counting Hard, and Deep Trees Make it Harder.
CONGRATULATIONS to Shaohua Li and Marcin Pilipczuk (University of Warsaw, Poland) who have been awarded an IPEC 2021 Best Paper Award for their paper, Hardness of Metric Dimension in Graphs of Constant Treewidth.
CONGRATULATIONS to Guillaume Ducoffe (University of Bucharest, Romania) who has been awarded an IPEC 2021 Best Paper Award for the paper, Maximum Matching in almost linear time on the graphs of bounded clique-width.
IPEC NEWS UPDATE. The selected list of 25 papers for IPEC 2021 is now online. ALGO 2021 and IPEC 2021 are fully online this year. The program is not public yet, but IPEC will take place September 8-10, and the sessions will be starting at 13:00 (Lisbon time). The business meeting of IPEC is preliminary scheduled on Thursday September 9, 18:30 (Lisbon). The registration is open now and is free for non-presenting attendees.
CONGRATULATIONS to Jason Crampton, Eduard Eiben, Gregory Gutin, Daniel Karapetyan, Diptapriyo Majumdar (Royal Holloway, University of London) who were awarded Best Paper Award at the 26th ACM Symposium on Access Control Models and Technologies (SACMAT 2021). Their paper, Valued Authorization Policy Existence Problem, proves some FPT and W[1]-hardness results for a new access control problem.
CONGRATULATIONS Benjamin M. Bumpus, Kitty Meeks (University of Glasgow) who have received the Best Paper Award at IWOCA 2021 - 32nd International Workshop on Combinatorial Algorithms, for their paper, Edge exploration of temporal graphs.
The paper introduces a natural temporal analogue of Eulerian circuits and proves that, in contrast with the static case, it is NP-hard to determine whether a given temporal graph is temporally Eulerian even if strong restrictions are on the structure of the underlying graph and each edge is active at only three times. However, the paper shows an FPT-algorithm with respect to a new parameter called interval-membership-width which restricts the times assigned
to different edges. This parameter will be of independent interest for other temporal graph problems.
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 30, 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.
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 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 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022)
WHEN: Conference March 24 - March 26, 2022
WHERE: at the University of Jember, Indonesia
Paper submission deadline: September 28, 2021 (Anywhere on Earth)
Based on the COVID-19 situation at the time of the conference, the event will be held physically in hybrid mode or virtually.
AWARDS: Best Paper" and "Best Student Paper" will be awarded. A paper is eligible for the Best Student Paper if the paper is presented by an author, who is a full-time student. The best paper awards will be sponsored by Springer.
INVITED SPEAKERS:
Prof. Hans L. Bodlaender (Utrecht University and Technical University Eindhoven, The Netherlands)
Prof. Tiziana Calamoneri (University of Rome "Sapienza", Italy)
Prof. Takehiro Ito (Tohoku University, Japan)
The 27th International Computing and Combinatorics Conference (COCOON 2021)
will be held in National Cheng Kung University, Tainan, Taiwan
during October 24-26, 2021.
https://algorithm.csie.ncku.edu.tw/conference/cocoon2021/
Due to COVID-19, COCOON 2021 will be a hybrid conference with both online and onsite participants. In case that the live on-line talk is not smooth, a pre-recorded talk will be played.
Original research papers in the areas of algorithms, theory of computation, computational complexity, and combinatorics related to computing are solicited. In addition to theoretical results, we are also interested in submissions that report on experimental and applied research of general algorithmic interest. Special consideration will be given to research that is
motivated by real-world problems. Experimental and applied papers are expected to show convincingly the
usefulness and efficiency of the algorithms discussed in a practical setting.
Important dates:
Paper Submission Due: June 30, 2021
Notification of Acceptance: August 15, 2021
Camera-ready and Registration: August 31, 2021
Conference Dates: October 24-26, 2021
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)
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
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.