School in Algorithms, Combinatorics, and Complexity
(https://indico.eimi.ru/event/199/ <https://indico.eimi.ru/event/199/>) (SACC), held from 24 May to 28 May, 2021, online.
SACC is organized by St. Petersburg State University and Euler International Mathematical Institute. The school will consist of three mini-courses given by:
Maria Chudnovsky (https://web.math.princeton.edu/~mchudnov/ <https://web.math.princeton.edu/~mchudnov/>);
Fedor Fomin (https://folk.uib.no/nmiff/ <https://folk.uib.no/nmiff/>);
Madhu Sudan (http://madhu.seas.harvard.edu/ <http://madhu.seas.harvard.edu/>).
The school is primarily intended for graduate, master, and senior bachelor students of any mathematical
speciality, but other participants are also welcome. The working language of the school is English.
APPLICATION AND COST: The application is free. The application deadline is 23 May, 2019. Please see https://indico.eimi.ru/event/199/ <https://indico.eimi.ru/event/199/> for more information.
WEBPAGE: https://indico.eimi.ru/event/199/ <https://indico.eimi.ru/event/199/>
CONTACT: Dmitry Sokolov: moc.liamg|tmd.volokos#moc.liamg|tmd.volokos <mailto:sokolov.dmt@gmail.com>/ <https://folk.uib.no/nmiff/>);
Congratulations to Damir Ferizovic, who has won the German Science Foundation (DFG) Young Talent Award for his Master Thesis "Engineering Kernelization for the Maximum Cut Problem". The main message of Damir's thesis is that kernelization (if carefully engineered) can speed up max cut computation by two orders of magnitude when compared to the performance of state-of-the-art solvers which have been carefully engineered for many years. The award was made at the Annual Meeting of the SPP 1736 Priority Programm "Algorithms for Big Data" of the DFG. Damir is the MSc student of Matthias Mnich. Damir has won many awards, including the 2019 1st Place: Internal Microsoft Hackathon. He is currently a Microsoft software engineer in Redmond, Washington. See his blog at https://www.damirferizovic.com/
IPEC 16 CALL FOR PAPERS
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
Important Dates
Paper Registration: June 25, 2021 (23:59 AoE)
Full Paper Submission: June 28, 2021 (23:59 AoE)
Notification of acceptance: July 30, 2021
Camera-ready: TBA, 2021
Conference dates: September 8-10, 2021
Program Committee Co-chairs:
Meirav Zehavi, Ben-Gurion University of the Negev, Israel
Petr Golovach , University of Bergen, Norway
++ EATCS-IPEC Nerode Prize - Call for Nominations - Deadline: April 15, 2021
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 2021 will be part of ALGO 2021, September 8-10, 2021, Lisbon, Portugal. 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:
Virginia V. Williams (Chair, MIT, ude.tim|igriv#ude.tim|igriv),
Anuj Dawar (University of Cambridge, ku.ca.mac.lc|rawad.juna#ku.ca.mac.lc|rawad.juna)
Fedor Fomin (University of Bergen, on.biu.ii|nimof#on.biu.ii|nimof)
Deadline for Nominations: April 15, 2021.
Decision: June 15, 2021.
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.
Eligibility: Any research paper or series of research papers by a single author or a team published in a recognized refereed journal. The research 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”.
--
CONGRATULATIONS TOBY WALSH, Scientia Professor of Artificial Intelligence at UNSW, and leader of the Algorithmic Decision Theory group at Data61. Toby has received the Donald E. Walker Distinguished Service Award at IJCAI-20.
Professor Walsh is recognized for his substantial contributions, as well as his extensive service to the field of Artificial Intelligence throughout his career.
World Logic Day: 14 January 2021. Vienna World Logic Day Lecture:
Speaker: Georg Gottlob (University of Oxford, TU Wien)
Title: Knowledge Processing, Logic, and the Future of AI
Date: 14 January 2021
Time: 8am PST | 11am EST | 1pm GMT-3 | 5pm CET
Digital venue: Zoom or YouTube
Thinking "fast" and "slow" on the reading list of the machines? Georg Gottlob´s Vienna World Logic Day Lecture addresses advances in the interaction between logical reasoning and machine learning leading to powerful and fair automated decision-making, among others.
Ambassadors of Logic: Renowned logicians from the fields of computer science, philosophy, mathematics, artificial intelligence give short statements on the WLD. This is what they have to say: https://logicday.vcla.at
UNESCO proclaimed World Logic Day in 2019, in association with the International Council for Philosophy and Human Sciences (CIPSH), to enhance public understanding of logic and its implications for science, technology and innovation. "In the twenty-first century - indeed, now more than ever - the discipline of logic is a particularly timely one, utterly vital to our societies and economies. Computer science and information and communications technology, for example, are rooted in logical and algorithmic reasoning." - Audrey Azoulay, Director General of UNESCO
Visit the website of Vienna World Logic Day at: https://logicday.vcla.at/
SOCIAL CHOICE SEMINAR SERIES. Arkadii Slinko, Director, Center for Mathematics in Social Sciences, Univ. Auckland.
Upcoming seminars and time slots where you can volunteer to give a talk.
https://sites.google.com/view/2021onlinescwseminars/schedule
Website created by Simona Fabrizi and Marcus Pivato.
The WG 2021 conference is the 47th edition of the WG series and will take place from Wednesday 23rd June to Friday 25th June 2021. Depending on the pandemic situation, the event will be organized at Old Library of University of Warsaw in Poland or as an online conference. Some hybrid form is also possible and even if the conference takes place in Warsaw, it will
be possible to give an online talk and participate online. The final decision about the form of the conference will be announced in February 2021, before the submission deadline.
Conference website: https://wg2021.mimuw.edu.pl
== INVITED SPEAKERS ==
Édouard Bonnet (CNRS, ENS Lyon, France)
Vida Dujmović (University of Ottawa, Canada)
Wojciech Samotij (Tel Aviv University, Israel)
== IMPORTANT DATES ==
Submission of papers: 3 March 2021
Acceptance notification: TBA (late April 2021)
Conference: 23-25 June 2021
Final version: TBA (middle of July 2021)
CONGRATULATIONS to Roohani Sharma (Institute of Mathematical Sciences) for the ACM India Doctoral Dissertation Honorable Mention Award, for her dissertation "Advancing the Algorithmic Tool-kit for Parameterized Cut Problems."
Roohani's advisor was Saket Saraubh. She is now a researcher at Max Planck Institute for Informatics.
CONGRATULATIONS to Shikhar Vashishth (Indian Institute of Science) for receiving the ACM India Council's 2021 Doctoral Dissertation Award for "Neural Graph Embedding Methods for Natural Language Processing." The award is accompanied by a prize of ₹2,00,000. The dissertation(s) will be published in the ACM Digital Library. Shikhar is currently working as a Postdoctoral Researcher at Language Technologies Institute, Carnegie Mellon University under Carolyn Rose. He completed his PhD from Indian Insitute of Science under the guidance of Partha Pratim Talukdar, Chiranjib Bhattacharyya, and Manaal Faruqui.
CONGRATULATIONS TO Saket Saurabh (Institute of Mathematical Sciences and University of Bergen). The Association for Computing Machinery (ACM) India Council has selected Saket as the recipient of the 2020 ACM India Early Career Researcher (ECR) Award (https://india.acm.org/awards/early-career-researcher-award). A selection committee comprising eminent international personalities chose Saket for this inaugural edition of the award.
The ACM India ECR Award recognizes individuals in early stages of their careers who have made fundamental, innovative, and impactful contributions to the computing field while primarily working in India. The winner of the ECR award receives a prize of Rs15 lakhs. The Honorable Mention award carries a prize of Rs7.5 lakhs. Financial support for both of these awards is provided by Persistent Foundation (https://www.persistentfoundation.org).
Saket is recognized for his fundamental contributions to the area of Parameterized Complexity, including methods for showing algorithmic lower bounds, and meta-theorems for polynomial time preprocessing. His work over the last decade can be characterized by these contributions, establishing him as an outstanding researcher, educator, and scientific leader:
* performing research of the highest quality in multiple areas of algorithms;
* leading the field of parameterized complexity by initiating new research directions to the community;
* mentoring students pursuing undergraduate and graduate to postdoctoral fellowships;
* sharing his knowledge in the form of new courses, lecture notes, surveys, schools, and workshops; and
* serving the community in conference program committees and journal editorial boards.
Saket received his PhD in Theoretical Computer Science from the Institute of Mathematical Sciences, Chennai. After spending a couple of years as a postdoc at the University of Bergen, Norway, he joined his alma mater for a faculty position, where he is currently a Professor. He is also a Visiting Professor at the University of Bergen.
CONGRATULATIONS to M.S. Ramanujan (MSR) (Univ Warwick, UK) who has received an EPSRC New Investigator Award for his project, PARITY: New Frontiers in Parameterizing Away from Triviality (https://msramanujan.weebly.com/parity-project.html) with a 2 year Postdoc position attached to it. Apply now.
The project asks: What if an observed network is not contained in a specific graph class, but resembles the graphs in this class, except for a few differences? Could one lift efficient algorithms that work on this graph class, to efficient algorithms for those graphs that are not contained within the classes, yet are still reasonably "close" to it? For example, suppose that we want to query for a smallest set of vertices that are cumulatively incident on all the edges in our graph. If our graph is a complete graph, then this query can be answered efficiently. But what if our graph is "close" to complete, that is, except for a few pairs of vertices, every other pair of vertices has an edge linking them? Could the same query still be answered efficiently? The answer turns out to be, yes!
This project aims to take a significant stride forward in this area by formally introducing new and more complex notions of graph edit distance and studying their impact on efficient solvability of NP-hard problems. These notions of edit distance will depend not on the number of edit operations as they traditionally have, but on their inherent structure. The success of parameterized complexity has shown that studying the structure of relevant objects as opposed to only considering their size, can have a powerful impact on efficient solvability of computational problems. In summary, this project will lay the foundations for an advanced algorithmic theory built on "structural edit distances" between graphs, develop new algorithms for fundamental problems and uncover hitherto unknown efficiently solvable instances.
CONGRATULATIONS TO EATCS-IPEC NERODE PRIZE WINNERS 2020.
• Marx, D.: "Parameterized graph separation problems". Theoretical Computer Science 351(3), 394–406 (2006)
• Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.: "A fixed-parameter algorithm for the directed feedback vertex set problem". J. ACM 55(5) (2008)
The concept of important separators, and the related concept of important cuts have become elegant and efficient tools frequently used to establish the fixed parameter tractability of graph problems. The first awarded paper introduces the notion of important separators and establishes many combinatorial and algorithmic insights. The paper gives a combinatorial bound on the number of important separators, and then uses this bound to obtain multiple important algorithmic applications. To accomplish this, the paper provides elegant proofs that show that optimal solutions contain an important separator with specific characteristics. The approach is robust in the sense that it works for a large variety of problems.
After the framework was established, several followup papers showed fixed parameter tractability for well-studied graph problems using the new technology, while introducing refinements and extensions of the techniques. The second awarded paper is a striking example of this, giving the first FPT algorithm for the famous directed feedback vertex set problem, thus solving one of the most important and long-standing open problems of the field.
CONGRATULATIONS BEST PAPER AND BEST STUDENT PAPER IPEC 2020 AWARD WINNERS!
Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná and Karolina Okrasa
Vertex deletion into bipartite permutation graphs
Tuukka Korhonen
Finding Optimal Triangulations Parameterized by Edge Clique Cover
PACE 2021 Call for Participation
Announcing the sixth iteration of PACE, the Parameterized Algorithms and Computational Experiments Challenge. The goals of PACE as well as official reports for past challenges can be found on website: https://pacechallenge.org/.
This year, the challenge is on Cluster Editing:
- Input: An undirected graph
- Output: A cluster editing set of minimum cardinality.Here, a cluster editing set is a set of edge modifications (addition or deletion) that transforms the graph into a cluster graph (each connected component is a clique)
Three tracks are planned:
1. Exact: Compute a cluster editing set of minimum cardinality. You have 30 minutes per instance. Contestants are ranked by number of instances solved and time required.
2. Heuristic: Compute some cluster editing set of decent cardinality. You have 10 minutes per instance. Contestants are ranked by quality of results and time required.
3. Kernelization: Compute an equivalent smaller instance. You have 5 minutes per instance. Contestants are ranked by size of the returned instance.
Detailed ranking method will be published online. Detailed instructions and public instances will be published later (see Timeline below)
PRIZES: Thanks to the generous sponsoring of the NETWORKS project (http://thenetworkcenter.nl/) prize money is available for the winners of the competition.
TIMELINE
- October 22nd, 2020: Announcement of the challenge (Problem)
- November 20th, 2020: Announcement of the tracks and additional information
- December 16th, 2020: Public instances are available
- TBA / March 2021: Submission via optil.io is open (for testing and unofficial, auxiliary leaderboard)
- TBA / May/June 2021 (AOE): Submission of the final version (solver description due two weeks after the source code)
- TBA / July 2021: Announcement of the results
- TBA / September 6-10, 2021: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2021)
PROGRAM COMMITTEE: André Nichterlein (mailto:andre.nichterlein@tu-berlin.de) (chair), (Technische Universität Berlin)
Leon Kellerhals (Technische Universität Berlin), Tomohiro Koana (Technische Universität Berlin), Philipp Zschoche (Technische Universität Berlin)
STEERING COMMITTEE:
- Édouard Bonnet (LIP, ENS Lyon)
- Holger Dell (Goethe University Frankfurt and IT University of Copenhagen)
- Johannes Fichte (Technische Universität Dresden)
- Markus Hecher (Technische Universität Wien)
- Bart M. P. Jansen (chair) (Eindhoven University of Technology)
- Petteri Kaski (Aalto University)
- Łukasz Kowalik (University of Warsaw)
- Marcin Pilipczuk (University of Warsaw)
- Manuel Sorge (Technische Universität Wien)
The latest Parameterized Complexity Newsletter is on the Newsletter page. Enjoy! Congratulations to all for awards, graduates, new jobs, and research. Read two research articles: Parameterized Algorithmics for Temporal Graph Problems by Hendrik Molter (TU Berlin) and Phylogenetics and parameterized complexity by Steven Kelk (Maastricht Univ). Update Wikipedia with your results. Add your presentations to the FPT Complexity Youtube. Contact Jungho Ahn (Kaist) rk.ca.tsiak|nhaohgnuj#rk.ca.tsiak|nhaohgnuj for assistance. Send us news via our new Google form (https://forms.gle/sfZNzKFsbfqSywgy7) or directly to our emails. We love hearing from you.
Editors: Frances.Rosamond@uib.no, Valia Mitsou rf.firi|uostimv#rf.firi|uostimv, Benjamin.Bergougnoux@uib.no and the News Team.
CONGRATULATIONS Michal Pilipczuk (Univ of Warsaw) for winning an ERC Starting Grant for his project, Decomposition methods for discrete problems (BOBR), which studies structural and decomposition
properties of networks and seeks general-purpose techniques that solve whole classes of problems, e.g. expressible in various kinds of logic. The ERC is 1,355,688 euro over 5 years.
CONGRATULATIONS Akanksha Agrawal (IIT Madras), who is a Rising Star at STOC. While a postdoctoral student at the department of computer
science under the instruction of Meirav Zehavi (Ben-Gurion Univ), Akanksha was selected to give a Rising Star presentation at the TCS Women Spotlight Workshop, part of the 52nd Annual ACM Symposium on the Theory of Computing (STOC 2020). Akanksha has joined IIT Madras as an assistant professor.
CONGRATULATIONS Neeldhara Misra (Indian Institute of Technology Gandhinagar) for being awarded
the INAE Young Engineer Award. The INAE Award is instituted to identify, recognize and encourage young and promising talents in India who have made and are likely to continue to make outstanding contributions impacting engineering research and design, technology development and transfer. The Award includes a prize of Rs.1 lakh and a citation. All INAE Young Engineer Awardees also become INAE Young Associates.
CONGRATULATIONS Steven Kelk (Maastricht Univ) who has received a grant from the Dutch scientific organization NWO for his project, Deep kernelization for phylogenetic discordance. The 267,000 euros grant finances a PhD student for 4-years.
Kelk's project seeks to aggressively reduce the size of kernels for various problems in phylogenetics, particularly for measuring the dissimilarity of two phylogenetic trees, and to leverage this in a wider algorithmic framework. (branch and reduce and so on). The launching point is joint work with Simone Linz (Univ Auckland) described by Kelk in a presentation given at Oxford last year. http: skelk.sdf-eu.org/Oxford_Kelk_2019_Web.pdf. The project builds on joint work with Linz, although she is not formally involved with this grant.
CONGRATULATIONS Tomás Peitl and Stefan Szeider (TU Wien) for winning the Best Paper Award at the main track of CP'2020, the 26th International Conference on Principles and Practice of Constraint Programming, for their paper: Finding the Hardest Formulas for Resolution. In the paper, a resolutionbased method (CDCL SAT solver) is used to find the hardest formulas for resolution, which constitutes a self reference. The paper is available at https://www.ac.tuwien.ac.at/2020/09/
best-paper-award-at-cp2020/
CONGRATULATIONS to Ronald deHaan on his new book.
"Parameterized Complexity in the Polynomial Hierarchy: Extending
Parameterized Complexity Theory to Higher Levels of the Hierarchy",
Springer (2020). Free preview at Springer, and it is even on Kindle!
Parameterized Complexity in the Polynomial Hierarchy was co-recipient of the E.W. Beth Dissertation Prize 2017 for outstanding dissertations in the fields of logic, language, and information. This work extends the theory of parameterized complexity to higher levels of the Polynomial Hierarchy (PH). For problems at higher levels of the PH, a promising solving approach is to develop fixed-parameter tractable reductions to SAT, and to subsequently use a SAT solving algorithm to solve the problem. In this dissertation, a theoretical toolbox is developed that can be used to classify in which cases this is possible. The use of this toolbox is illustrated by applying it to analyze a wide range of problems from various areas of computer science and artificial intelligence.
CONGRATULATIONS to Julien Baste, who has obtained a position as Assistant Professor in Lille, north of France. This is a permanent position in France. All our very best wishes to Julien.
CONGRATULATIONS to Fábio Protti, who has been made a full professor at the Institute of Computing of Fluminense Federal University. Colleague Celina de Figueiredo reports that there was a beautiful and touching ceremony which took the whole of Wednesday afternoon. All our very best wishes to Fábio.
PUBLIC DEBATE: The Future of Conferences in Theoretical Computer Science
DATE: Wednesday 2 September
TIME: 3pm UTC / 8am San Francisco / 10am Houston / 11am Philadelphia / 4pm London / 5pm Paris / 9pm Mumbai / 11pm Beijing / midnight Tokyo / 1am Sydney
CONTACT: Nathanaël Fijalkow <rf.irbal|woklajif.leanahtan#rf.irbal|woklajif.leanahtan>
The entire community is invited to participate in a debate on the future of the conference system in theoretical computer science. Organized as a special event as part of the Online Worldwide Seminar on Logic and Semantics (OWLS), this will provide a rare community-wide opportunity for us to consider the strengths and weaknesses of our current system, and consider if we can do better.
YOU PROPOSE A QUESTION
Questions will be asked by members of the community. That means you! Email Nathanael (above) to propose your question, which could raise any issue in scope. Make sure to use an academic email address. We'll let you know if your question is accepted, and you'll then have the opportunity to ask it during the debate, and to respond to the panel's comments.
The scope of the debate is all aspects of our publishing and community traditions, characterised by prestige earned mostly through publication in competitive conferences, and frequent local and international travel. Possible topics for discussion include the need to publish in conferences for career progression, which usually involves burning carbon; wasted author and reviewer effort when good papers are rejected from highly competitive conferences; the extent of our responsibility as a community to respond to climate change; alternative publishing models, like the journal-focussed system used in mathematics; high costs of conference travel and registration; virtual conference advantages, disadvantages and best practice; improving equality, diversity and access; consequences and response to COVID-19; and the role of professional bodies. These topics have many close relationships, and need to be discussed together to gain a full understanding of the issues involved, and how we can move forward.
PANEL DISCUSSANTS:
- Dr Brendan Fong, MIT (brendanfong.com)
- Professor Delia Kesner, University of Paris (irif.fr/~kesner)
- Professor Benjamin Pierce, University of Pennsylvania (cis.upenn.edu/~bcpierce)
- Professor Moshe Vardi, Rice University (cs.rice.edu/~vardi)
ZOOM AND WEBSITE: The event will take place on Zoom at the following address, with no password or registration required:
- zoom.us/j/177472153
The debate will be followed by an opportunity to discuss informally with other members of the community in small groups.
This event is organized as part of the OWLS seminar series. For more information, a calendar you can embed into your own, and to sign up for reminder emails, visit the webpage:
- https://www.cs.bham.ac.uk/~vicaryjo/owls/
READING: Members of the community may enjoy the following articles, related to the topic of the debate.
- Lance Fortnow (2009), "Time for Computer Science to Grow Up",
https://cacm.acm.org/magazines/2009/8/34492-viewpoint-time-for-computer-science-to-grow-up
- Benjamin Pierce, Michael Hicks, Crista Lopes and Jens Palsberg
(2020), "Conferences in an Era of Expensive Carbon",
https://cacm.acm.org/magazines/2020/3/243024-conferences-in-an-era-of-expensive-carbon
- Moshe Vardi (2020), "Publish and Perish",
https://cacm.acm.org/magazines/2020/1/241717-publish-and-perish
CONGRATULATIONS to Robert Ganian (Vienna University of Technology (TU Wien)) for the START project "Parameterized Analysis in Artificial Intelligence" funded by the FWF Austrian Science Fund. The aim of the project is to build a bridge between parameterized complexity theory and artificial intelligence. A PhD position is available. Applications or informal enquiries and questions about the position should be sent to moc.liamg|nainagr#moc.liamg|nainagr before August 30.
The Vienna Center for Logic and Algorithms of TU Wien (VCLA) has the pleasure to announce the recipients of the VCLA International Student Awards for Outstanding Master and Undergraduate Theses in Logic and Computer Science.
OUTSTANDING MASTER THESIS AWARD: Karolina Okrasa (Poland Warsaw University of Technology) for thesis: Complexity of variants of graph homomorphism problem in selected graph classes. Under the supervision of Paweł Rzążewski.
OUTSTANDING UNDERGRADUATE RESEARCH AWARD: Antonin Callard (France ENS Paris-Saclay) for thesis: Topological analysis of represented spaces and computable maps, cb0 spaces and non-countably-based spaces. Under the supervision of Mathieu Hoyrup
http://www.vcla.at/2020/07/fifth-edition-of-the-vcla-international-student-awards-2020/
IPEC 2020: The submission deadline for the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) has been extended. The new deadlines are:
19th July (AoE) paper registration
22nd July (AoE) full paper submission
International Symposium on Parameterized and Exact Computation (IPEC) is an annual conference covering all aspects of parameterized and exact algorithms and complexity.
Its 15th edition will happen online in 2020.
http://apsec2012.comp.polyu.edu.hk/index.html
CONGRATULATIONS TO Bruno Courcelle who has won the 2020 S. Barry Cooper Prize for his work on the definability of graph properties in Monadic Second Order Logic, through a sequence of seminal papers and a book (joint with Joost Engelfriet). This forms an outstanding example of theory building, bringing together logic, computability, graph grammars, and various notions of graph width (tree-width, clique-width and rank-width) and opening new avenues in our understanding of graph structure theory and the computability and complexity of graph algorithms. Besides its foundational character, the work has had great impact on a number of areas of computer science, including in parameterized algorithmics, verification and other areas, and has influenced a generation of researchers in this field. It has straddled the divide between the logical and algorithmic aspects of theoretical computer science.
The award ceremony will take place on July 2nd during the Computability in Europe 2020 conference.
(https://www.acie.eu/cie-conference-series/cie2020) is mandatory to attend, but it is without fees.
The Barry Cooper Prize Committee 2019-2023
Anuj Dawar
Peter Van Emde Boas
Yuri Gurevitch
Mariya Soskova
Paola Bonizzoni
Nice video of Women in TCS Singing Together
WOMEN IN COMPUTER SCIENCE SING
https://www.youtube.com/watch?v=4Wl-3kadvgw
IPEC 2020: 15th International Symposium on Parameterized and Exact Computation, Hong Kong, China, December 14-18, 2020
Submission link https://easychair.org/conferences/?conf=ipec2020
Submission deadline July 15, 2020
Theoretically grounded studies on parameterized and exact computations and kernelization for real-world applications and algorithmic engineering are especially encouraged.
CONFERENCE WILL BE ONLINE: 14–18 December 2020. On each day, there will be two roughly 90-minute sessions of invited and contributed talks with a 30-minute break in between, scheduled between 8am and noon UTC (i.e., spanning European morning / Asian afternoon or evening). The conference will also feature virtual rooms for coffee break discussions. Participating in the conference will be free of charge.
Accepted papers will be published in the symposium proceedings in the LIPIcs series, based at Schloss Dagstuhl. Authors of accepted papers are expected to present their work at the symposium (preferably by a live online talk or at the very least by a prerecorded talk), and to incorporate the comments from the program committee. Authors are also encouraged to be present at virtual coffee breaks at least after the session with their talk.
A special issue of Algorithmica is planned for selected papers presented at IPEC 2020.
AWARDS: Best Paper Award and Excellent Student Paper Awards, 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 expected that a student gives a presentation at the conference. Papers co-authored by members of the programme committee are not eligible for the Best Paper Award or the Best Student Paper Award.
SPECIAL EVENTS: An invited talk is planned by the 2020 EATCS-IPEC Nerode Prize winner. There will be a session presenting the results of the 5th Parameterized Algorithms and Computational Experiments Challenge (PACE 2020).
NEW! NEW! NEW! PC BLOG!
This blog contains talks on Frontiers of Parameterized Complexity. The new plan is to have talks every alternate Thursday at 17.00 Bergen time (GMT+1).
https://uib.zoom.us/j/4231169675
Meeting ID: 423 116 9675
Password: name of the W[1]-complete problem, 6 letters, all capital. Set of pairwise adjacent vertices.
December 10, 2020 at 17:00 GMT+1
Parinya Chalermsook, Aalto University
Title: Vertex Sparsification for Edge Connectivity
Abstract: Graph compression is a basic information theoretic and computational question that has found its applications in many areas of algorithm design. In this work, we initiate the study of a parameterized variant of graph compression that preserves cut sizes between designated terminals. We present applications in designing fast dynamic graph algorithms and in the survivable network design problems in low treewidth graphs.
(Joint work with Syamantak Das, Bundit Laekhanukit, Yunbum Kook, Yang P. Liu, Richard Peng, Mark Sellke, Danial Vaz.)
The recordings of the previous talks are now available on YouTube channels Frontiers of Parameterized Complexity or FPT Complexity. The links to the available slides of the past talks can be found at https://frontpc.blogspot.com.
CONGRATULATIONS to Roohani Sharma, who has been awarded a Lise Meitner postdoctoral fellowship at MPI.
“Every year the Max Planck Institute for Informatics awards the Lise Meitner Award. This grant supports excellent female computer scientists in their careers, giving them the opportunity to develop their scientific ideas without exertion of influence. It consists of a two-year tax-free postdoctoral research fellowship including business expenses. This grant is according to the fellowship rules of the Max Planck Society: it usually amounts to 3,000 Euro/month and is completed by compensation for business expenses of 10,000 Euro/year.”
EATCS-IPEC Nerode Prize - DEADLINE EXTENDED for Nominations — NEW Deadline: APRIL 15, 2020
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 2020 takes place within ISAAC 2020, December 14-16, 2020, Hong Kong. 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: Hans L. Bodlaender (Chair, Utrecht University, ln.uu|rednealdob.l.h#ln.uu|rednealdob.l.h), Anuj Dawar (University of Cambridge, ku.ca.mac.lc|rawad.junA#ku.ca.mac.lc|rawad.junA), Virgi V. Williams (MIT, ude.tim|igriv#ude.tim|igriv).
Eligibility: 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.
Nominations: 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".
GROW SPECIAL ISSUE We invite submissions to the special issue of Discrete Applied Mathematics dedicated to the Ninth Workshop on Graph Classes, Optimization, and Width Parameters, GROW 2019, which took place in Vienna, Austria, in September 2019.
Submission is also open to researchers who did not attend GROW 2019, and the papers may, but need not, be related to a presentation at the workshop. Contributions arising from papers already published in conference proceedings should be substantially extended and should cite the conference presentation where appropriate. All articles will be thoroughly refereed according to the high standards of Discrete Applied Mathematics.
The full papers must be submitted through the Elsevier Editorial System (https://www.editorialmanager.com/DAM/default.aspx); please make sure to select the article type "Special Issue: GROW 2019". The deadline for submission is July 1, 2020. Accepted papers will be published online individually before print publication.
If you are considering submitting a paper to the special issue, please let us know via a brief email to ta.ca.neiwut.ca|9102worg#ta.ca.neiwut.ca|9102worg.
This call for papers is also available at: http://rutcor.rutgers.edu/CfP%20Grow%202019.pdf
Guest Editors: Robert Ganian, Jan Kratochvil, and Stefan Szeider
ICALP moved from China to Saarbruecken. See https://econcs.pku.edu.cn/icalp2020/
Thanks for reading, wash those hands, and have a great weekend.
Map for virus information here:
https://www.arcgis.com/apps/opsdashboard/index.html#/bda7594740fd40299423467b48e9ecf6
The 6th annual Scottish Combinatorics Meeting will be held at the University of Glasgow on Thursday 30th April and Friday 1st May 2020. For more details and a provisional programme, visit http://www.dcs.gla.ac.uk/~kitty/scm/.
Attendance at the meeting is free of charge, but for catering purposes we ask participants to register by 5th April 2020 (via the website). Limited funding available for UK-based research students to attend.
Financial support from the London Mathematical Society, the Glasgow Mathematical Journal Learning and Research Support Fund, and the Edinburgh Mathematical Society.
Contact: Kitty Meeks, University of Glasgow (http://www.dcs.gla.ac.uk/~kitty/) <ku.ca.wogsalg|skeem.yttik#ku.ca.wogsalg|skeem.yttik>
Application deadline: April 22, 2020 for the The Steven H. Strogatz Prize for Math Communication
High school students 15 to 18 years of age as of September 1, 2019 share your love of math with the world. Enter this worldwide contest!
Cash prizes will be awarded for compelling math communication projects, and award-winning projects will be posted online.
Projects will be accepted in the following categories:
Video
Audio
Social media
Art
Writing
Performance
Examples include: podcasts, articles, school newspaper columns, art exhibits, YouTube videos, websites, Instagram accounts, songs, plays, and any other mode of public communication.
Projects will be judged based on Content, Creativity, Communication.
Submission information: https://momath.org/the-steven-h-strogatz-prize-for-math-communication/
Please email questions to gro.htamom|ezirpztagorts#gro.htamom|ezirpztagorts.
NOMINATION - SELF NOMINATION IS FINE - of authors of outstanding theses and scientific works in the field of Logic and Computer Science. The Vienna Center for Logic and Algorithms of TU Wien (Vienna University of Technology) announces awards in the following two categories:
=Outstanding Master Thesis Award
=Outstanding Undergraduate Thesis Award (Bachelor thesis or equivalent, 1st cycle of the Bologna process)
*SUBMISSION DEADLINE EXTENDED: April 9, 2020
Contact: Please send all inquiries to award (AT) logic-cs.at
Previous Awardees and Nomination instructions: https://logic-cs.at/vcla-awards-2020/
The award is dedicated to the memory of Helmut Veith, the brilliant computer scientist who tragically passed away in March 2016, and aims to carry on his commitment to promoting young talent and promising researchers in these areas.
*The Outstanding Master Thesis Award: 1200 EUR *The Outstanding Undergraduate Thesis Award: 800 EUR *The winners will be invited to present their work at an award ceremony in Vienna.
Final Call for Papers: 15th INTERNATIONAL COMPUTER SCIENCE SYMPOSIUM IN RUSSIA (CSR 2020). June 29 - July 03, 2020, Ekaterinburg, Russia (https://csr2020.sciencesconf.org/) Previous CSR conferences can be found at https://logic.pdmi.ras.ru/~csr/
Deadline for abstract submissions is January 10th, 2020 Deadline for paper updates: January 16th, 2020
DISTINGUISHED OPENING LECTURE Bela Bollobas (University of Cambridge and University of Memphis, USA)
INVITED SPEAKERS
Farid Ablaev (Tartastan Academy of Sciences, Russia)
Ulrik Brandes (ETH Zürich, Switzerland)
Piotr Faliszewski (AGH University of Science and Technology, Krakow, Poland)
Mateus de Oliveira Oliveira (University of Bergen, Norway)
Meirav Zehavi (Ben Gurion University, Israel)
Binhai Zhu (Montana State University, USA)
TOPICS include, but are not limited to: algorithms and data structures, computational complexity, including hardness of approximation and parameterized complexity, randomness in computing, approximation algorithms, fixed-parameter algorithms, combinatorial optimization, constraint satisfaction, operations research, computational geometry, string algorithms, formal languages and automata, including applications to computational linguistics, codes and cryptography, combinatorics in computer science, computational biology, applications of logic to computer
science, proof complexity, database theory, distributed computing, fundamentals of machine learning, including learning theory, grammatical inference and neural computing, computational social choice, quantum computing and quantum, cryptography, theoretical aspects of big data.
EARLY CALL FOR PARTICIPATION:
8th Summer Workshop, The Centre for Mathematical Social Science (CMSS) at The University of Auckland, 18-19 February, 2021.
Title: Preferences on restricted domains and their aggregation. While in any human society, restricting voters' opinions to those from a certain restricted domain looks unrealistic, economics is able to provide to Artificial Intelligence research a valuable insight for the design of artificial societies of autonomous software agents that are intended to constructively deal with the problem of intransitivity of group preference.
Invited speakers: - Edith Elkind (Oxford, UK) and Clemens Puppe (Karlsruhe Institute of Technology, Germany).
Formal presentations will be accompanied by research collaborations in small groups with participation from visitors and local researchers, including PhD students. The proposed topics for these small group sessions are yet to be determined but may, for example, include:
- mathematics of Condorcet domains in general;
- classification of small Condorcet domains with certain additional requirements, e.g., connected and of maximal width;
- complexity of voting rules on various Condorcet domains;
- generalisations of single-peakedness and single-crossingness;
- simple permutations and their role in classification of never-middle Condorcet domains.
On the second day of the workshop will be devoted to applications where the problem of intransitivity manifests itself.
There is no participation fee. There will be a workshop dinner on the first day the cost of which will be announced later. If you are thinking of participating or have any questions please contact
Prof. Arkadii Slinko
Department of Mathematics
The University of Auckland,
Centre for Mathematics in Social Sciences
zn.ca.dnalkcua|oknils.a#zn.ca.dnalkcua|oknils.a
It is time for everyone to update any WIKIPEDIA pages related to Parameterized Complexity, particularly those related to your research. If there is no page, please start one. Use the Doodle to let us know which pages have been updated.
More information about the project can be found in the slides from the IPEC 2019 business meeting.
PACE WINNERS 2019
CONGRATULATIONS to the Parameterized Algorithms Computational Experiments (PACE 2019) winning teams and participants. Read all about it in the PACE 2019 REPORT by Johannes K. Fichte and Markus Hecher (co-chairs), which is in Vol 15(2) October 2019 Parameterized Complexity Newsletter (see the Newsletter Page on this wiki).
JOIN the FIFTH ITERATION of PACE, the Parameterized Algorithms and Computational Experiments Challenge. The goals of PACE as well as official reports for past challenges can be found at: https://pacechallenge.us14.list-manage.com/track/click?u=099a5247e11f3ec74647f6a19&id=8f6bb5d773&e=7f05a0ce9c.
This year, the challenge is on treedepth (for an explanation with figures see https://pacechallenge.us14.list-manage.com/track/click?u=099a5247e11f3ec74647f6a19&id=59263b27b5&e=7f05a0ce9c):
- Input: A connected undirected graph
- Output: A treedepth decomposition of the graph
Two tracks are planned:
1. Exact: Compute a treedepth decomposition of minimum depth.
2. Heuristic: Compute some treedepth decomposition of decent depth..
Detailed instructions, definitions, public instances, timeline are available on the PACE website: https://pacechallenge.org
BEST PAPER AWARDS
CONGRATULATIONS to Cornelius Brand (Saarland University) winner of the best student paper award of Track A at ESA 2019 for his paper, Patching Colors with Tensors, involving PC.
CONGRATULATIONS to Giordano Da Lozzo, David Eppstein, Michael Goodrich and Siddharth Gupta, winners of the IPEC 2019 Best Paper Award, for their paper C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width.
CONGRATULATIONS to Gregory Rosenthal (University of Toronto) winner of the IPEC 2019 Excellent Student Paper Award, for his paper, Beating Treewidth for Average-Case Subgraph Isomorphism.
CONGRATULATIONS to William Lochet for being awarded the Charles Delorme Graphs Thesis Prize
for an excellent dissertation in Graphs (theory and algorithmic) in a French school or university. The Prize comes with an award of euro 1,500.
BUILDING BRIDGES BETWEEN PRACTICAL COMPUTING AND PARAMETERIZED COMPLEXITY (PCPC) WORKSHOP. August 5—9, 2019 in Bergen, Norway.
The objective of the workshop is to build bridges between parameterized complexity theory and practical applications.
WEBSITE: https://www.uib.no/en/rg/algo/127995/parameterized-complexity-and-practical-computing-workshop
KEYNOTE SPEAKERS AND THEIR APPLICATION AREAS:
• Prof. Gregory Gutin (Royal Holloway, University of London) - Di-graphs, Computer Security-Cryptography, Workflow Satisfiability.
• Prof. Klaus Jansen (University of Kiel, Germany) - Scheduling problems
• Prof. Blair Sullivan (Univ Utah, Oak Ridge National Laborator, USA) -Data-driven science: Computational neuroscience, quantum computing, biomechanical engineering, cybersecurity, social networks.
LOCATION AND DATES
• Dates: The workshop will take place in Bergen, Norway during the week starting Monday 05 August, 2019.
• Place: The first two days (Monday and Tuesday, 05 and 06 August) will be held at the Solstrand Hotel.
• Place: Day 3 (Wednesday 07 August) will be a fjord trip offering the opportunity for continued discussion. See below.
• Place: Days 4 and 5 (Thursday and Friday, 08 and 09) talks will be presented at the University of Bergen.
SUBMISSIONS
The workshop aims to bring together researchers and practitioners of Parameterized algorithms to share their perspectives and experiences. We solicit submissions describing research results with practical applications, and position statements leading to new directions, standpoints, and learned lessons. There will be long (40 minute) and short (20 minute) talks and discussion time. Exact format TBA.
ABSTRACT and REGISTRATION
Submit an abstract with your preference for length of talking time to: Mateus De Oliveira Oliveira <on.biu|arievilO.suetaM#on.biu|arievilO.suetaM>. In the Subject line put the words: PCPC REGISTRATION.
There is no fee for the workshop.
The following expenses will be covered by Mike Fellows' Norwegian Toppforsk Grant:
• Accommodation to all participants for one night (August 05 to August 06) at the Solstrand Hotel. Meals are provided at the hotel.
• Buses from UiB to the workshop venue on the morning of August 05 and back to UiB on the evening of August 06.
• Taxis from the airport to Solstrand Hotel for people arriving at Bergen airport on the morning of August 05. If you are contemplating this possibility please make taxi arrangements through the hotel so that the hotel can arrange joint taxi if suitable.
• Fjord trip outing on Wednesday to continue discussions.
Fjord Trip on Wednesday, Day 3
There will be a cruise trip to the fjords on Wednesday, 07 July. The cruise will pass through deep fjords, steep mountains, mighty waterfalls, and powerful currents. The duration of the trip is about 3 hours.
• The cruise is called Fjordcruise Bergen-Mostraumen.
• The departure is from Zachariasbryggen quay at the Fish Market in Bergen. Boarding time to be announced.
FOR MORE INFORMATION CONTACT: on.biu|dnomasor.secnarF#on.biu|dnomasor.secnarF, on.biu|swollef.leahciM#on.biu|swollef.leahciM
Congratulations to Prof. Sang-il Oum (https://mathsci.kaist.ac.kr/~sangil/) who is the Director of the new IBS Discrete Mathematics Group (DIMAG) in Daejeon, Korea. DIMAG is a new research group established at the Institute for Basic Science (IBS, https://www.ibs.re.kr). DIMAG is located on the main campus of the Institute for Basic Science (IBS) in Daejeon, South Korea, a city of 1.5 million people.
Congratulations to Bingkai Lin who has won the 2019 ICALP Best Paper Award, Track A for A Simple Gap-producing Reduction for the Parameterized Set Cover Problem. Bingkai is a National-Youth-1000-Talent Professor in the Theory Group at Nanjing University. In the transition
period, He is also a researcher by special appointment at National Institute of Informatics.
Bingkai has also won the SODA 2015, best paper and best student paper awards with The Parameterized Complexity of k-Biclique (Journal of the ACM (JACM), Volume 65 Issue 5 (2018)).
ICALP Parameterized Approximation Algorithms Workshop (PAAW) on 8 July at the ICALP 2019 in Patras, Greece. Organizers: Andreas Emil Feldmann (Charles University, Prague, Czech Republic).
CFP: IPEC DEADLINE APPROACHES
DATES:
Title and short abstract registration deadline: May 29, 2019, 23:59 AoE
Full paper submission deadline: June 1, 2019, 23:59 AoE
Notification: July 15, 2019
Conference: September 11-13, 2019
Full details of the CFP can be found at https://easychair.org/cfp/ipec2019 .
PACE 2019 Second Call for Participation in the 4th iteration of PACE, the Parameterized Algorithms and Computational Experiments Challenge. See the new website: https://pacechallenge.org/ for detailed instruction and reports about past challenges.
This year, the PACE challenge consists of two separate tracks: Vertex Cover and Hypertree Width.
The goal of PACE is to investigate the applicability of algorithmic ideas studied and developed in the subfields of multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms.
Please distribute this announcement to any party that may be interested.
Track 1 (Vertex Cover)
a) Compute an optimal vertex cover. You have 30 minutes per instance.
Contestants are ranked by number of instances solved and time required.
Track 2 (Hypertree Width)
a) Compute an optimal hypertree decomposition (hypertree decomposition of minimum hypertree width). You have 30 minutes per instance.
Contestants are ranked by number of instances solved and time required.
b) Compute some hypertree decomposition of decent hypertree width. You have 30 minutes per instance. Contestants are ranked by quality of results and time required. Exact ranking method will be published online.
Prizes
Thanks to the generous sponsoring of the NETWORKS project, a total of 4750 Euro of prize money and travel support is available for the winners of the competition.
Timeline
- December 10th, 2018: Public Hypertree Width instances online
- January 7th, 2019: Public Vertex Cover instances online
- May 2nd, 2019: Submission of final version
- July 1st, 2019: Announcement of the results
- September 11-13, 2019: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2019) in Munich
Program Committee
- Johannes Fichte (TU Dresden, Germany)
- Markus Hecher (TU Vienna, Austria)
Steering Committee
- Édouard Bonnet (Middlesex University, London)
- Holger Dell (Saarland Informatics Campus)
- Bart M. P. Jansen (chair) (Eindhoven University of Technology)
- Thore Husfeldt (ITU Copenhagen and Lund University)
- Petteri Kaski (Aalto University)
- Christian Komusiewicz (Philipps-Universität Marburg)
- Frances A. Rosamond (University of Bergen)
- Florian Sikora (LAMSADE, Université Paris Dauphine)
CONGRATULATIONS to Prof. Dr. Tobias Friedrich (Hasso Plattner Institute, Univ Pottsdam) who has been made Academic Dean. Tobias has been the Head of the Algorithm Engineering group, which currently hosts six Post-Docs and thirteen PhD Students, with invitations for more to join.
WANTED: CO-EDITOR FOR THE PARAMETERIZED COMPLEXITY NEWSLETTER
Join Fran and Valia as a Co-Editor for the PC Newsletter. Benefits: Excellent opportunity to approach any FPTer, anywhere, and ask about their latest projects and research. Keep abreast of the advances and new directions of the field. Add to your CV (the Newsletter is increasingly being cited). Receive kudos and appreciation from the community. Tasks: Update the mailing list, gather news, award, conference information, choose and invite articles, assist in putting it all together. Contact on.biu|dnomasor.secnarf#on.biu|dnomasor.secnarf.
DEADLINE EXTENDED to 25/03/2019. NOMINATE outstanding Masters or Undergraduate Thesis for the VCLA International Student Awards. The Vienna Center for Logic and Algorithms (VCLA) of TU Wein annually award authors of scientific works across the wide spectrum of Logic and Computer Science. The degree must have been awarded between 15 Nov 2017 and 31 Dec 2018.
The main area of interest are:
• Computational Logic, covering theoretical and mathematical foundations
• Databases and Artificial Intelligence, concerned with logical methods for modeling, storing, and drawing inferences from data and knowledge. argumentation, planning).
• Verification, concerned with logical methods and automated tools for reasoning about the behavior and correctness of complex state-based systems such as software and hardware designs as well as hybrid systems.
For nomination instructions, please visit
<https://logic-cs.at/award-call-2019/> https://logic-cs.at/award-call-2019/
Inquiries: <mailto:award@logic-cs.at> ta.sc-cigol|drawa#ta.sc-cigol|drawa
Award Committee: Robert Ganian (committee co-chair), Magdalena Ortiz (general chair), Revantha Ramanayake (committee co-chair)
IN MEMORIAM: The award is dedicated to the memory of Helmut Veith, the brilliant computer scientist who tragically passed away in March 2016, and aims to carry on his commitment to promoting young talent and promising researchers in these areas.
IPEC 2019 CALL FOR PAPERS
IPEC 2019 will be part of ALGO 2019, which also hosts ESA 2019 and a number of more specialized conferences and workshops. IPEC 2019 will take place September 11-13, 2019, in Munich, Germany.
*Important dates*
Title and short abstract registration deadline: May 29, 2019, 23:59 AoE
Full paper submission deadline: June 1, 2019, 23:59 AoE
Notification: July 15, 2019
Conference: September 11-13, 2019
See the full call for papers for more information.
2019 CALL FOR NOMINATIONS: The EATCS-IPEC Nerode Prize For Outstanding Papers in Multivariate Algorithmics. Deadline: March 15, 2019
The EATCS-IPEC Nerode Prize is an annual prize for outstanding work in multivariate algorithmics and parameterized complexity, published in a recognized refereed journal by an individual or a team of authors. 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 Call for Nominations for 2019 EATCS-IPEC Nerode Prize is open. Please send your nomination via emails to the Prize Committee Chair Jianer Chen at ude.umat.esc|nehc#ude.umat.esc|nehc no later than March 15, 2019. The nomination should contain a brief summary of the technical content of the nominated paper and a brief explanation of its significance. The Subject line of the nomination E-mail should contain the group of words "Nerode Prize Nomination".
Note that the past rules that require a certain number of years before/after the publication of the nominated paper have been removed. Thus, nominations for any past work in this area that you feel deserves the recognition will be welcome.
The award presentation will take place at ALGO/IPEC 2019 (The 14th International Symposium on Parameterized and Exact Computation) September 11-13, 2019 in Munich, Germany.
The EATCS-IPEC Nerode Prize Committee: Jianer Chen <ude.umat.esc|nehc#ude.umat.esc|nehc> Award Committee Chair (Texas A&M University, USA), Hans L. Bodlaender <ln.uu|rednealdob.l.h#ln.uu|rednealdob.l.h>
(Utrecht University, The Netherlands), Virgi V. Williams ude.tim|igriv#ude.tim|igriv (MIT, USA)
CONGRATULATIONS to Mateus de Oliveira Oliveira (Univ Bergen, Norway). Mateus’ project Automated Theorem Proving from the Mindset of Parameterized Complexity has been granted by the Norwegian Research Council IKTPLUSS program: Young Research Talents. The Research Council's awards for young outstanding researchers reward high scientific merit, independence and innovative thinking, and are intended to motivate prize recipients at an early stage in their careers to expand their efforts and continue to pursue a career in research.
Visit the JOBS AVAILABLE page on this wiki.
CALL FOR PAPERS: 22nd Symposium on Fundamentals of Computation Theory (FCT). August 11–14, 2019 at the University of Copenhagen, Denmark. Abstract registration: March 31, 2019. Full-paper submission: April 7. Notification to authors: May 19. Camera-ready submission: June 2. Submit original research papers in all areas related to the foundations of computer science (algorithms, complexity, and formal methods). FCT was established in 1977. It is a biennial conference that circulates on a regular basis in Eastern Europe, Western Europe, and the Nordic countries.
NOMINATE outstanding Masters or Undergraduate Thesis for the VCLA International Student Awards. The Vienna Center for Logic and Algorithms (VCLA) of TU Wein annually award authors of scientific works across the wide spectrum of Logic and Computer Science. Deadline March 15, 2019. The degree must have been awarded between 15 Nov 2017 and 31 Dec 2018.
The main area of interest are:
• Computational Logic, covering theoretical and mathematical foundations
• Databases and Artificial Intelligence, concerned with logical methods for modeling, storing, and drawing inferences from data and knowledge. argumentation, planning).
• Verification, concerned with logical methods and automated tools for reasoning about the behavior and correctness of complex state-based systems such as software and hardware designs as well as hybrid systems.
For nomination instructions, please visit
<https://logic-cs.at/award-call-2019/> https://logic-cs.at/award-call-2019/
Inquiries: <mailto:award@logic-cs.at> ta.sc-cigol|drawa#ta.sc-cigol|drawa
Award Committee: Robert Ganian (committee co-chair), Magdalena Ortiz (general chair), Revantha Ramanayake (committee co-chair)
IN MEMORIAM: The award is dedicated to the memory of Helmut Veith, the brilliant computer scientist who tragically passed away in March 2016, and aims to carry on his commitment to promoting young talent and promising researchers in these areas.
Remember to NOMINATE: Presburger Award for Young Scientists.
Deadline: December 31st, 2018. Official website: http://www.eatcs.org/index.php/presburger
CONGRATULATIONS to Eduard Eiben, post-doc at Univ Bergen,
who was awarded the National Award of Excellence by the Austrian Federal Ministry of Education, Science and Research (BMBWF) for his outstanding dissertation. The award ceremony took place in Vienna on December 5th, 2018. Eduard Eiben has been awarded for his dissertation Exploiting new types of structure for fixed-parameter tractability. The work was carried out as part of a research project funded by the Austrian Science Fund FWF at the Institute for Logic and Computation at the Faculty of Informatics at TU Wien. The supervisors were Prof. Stefan Szeider and Dr. Robert Ganian.
Eduard Eiben is the first graduate of the Doctoral Program “Logical Methods in Computer Science” (LogiCS), which was founded in 2014 by professors at TU Wien, TU Graz, and JKU Linz.
I am particularly pleased that an algorithmic work has been awarded, because algorithms will in future gain an increasingly important role in technological innovation, says Prof. Georg Gottlob, the head of the LogiCS Doctoral College.
Workshop on Kernels 2019 will be held at University of Bergen, Norway,
on June 3-7 2019. Workshop on Kernels (WorKer) is an irregular meeting focused on kernelization: rigorous theory of preprocessing. The 2019 edition will be the sixth installment of the workshop, featuring a tutorial on coresets by Christian Sohler and a tutorial on lossy kernels.
For more information, in particular a tentative list of invited speakers, please visit http://worker2019.mimuw.edu.pl. Registration will open in early Spring 2019. Please feel free to forward this announcement to your students and colleagues.
CONGRATULATIONS to Vangelis Paschos (Lamsade, Univ Dauphine) for
receiving a Visiting Professorship in the Department of Management and Production Engineering (DIGEP) at the Univ of Torino. The department is the point of reference in Politecnico di Torino for research in the relationship between systems of production of goods and services and the economic environment in which they operate. The DIGEP promotes basic and applied research, training, technology transfer and services to the local community in the areas of systems of production, quality management, product design, management and accounting, industrial plants law and economics.
CONGRATULATIONS to Jessica Enright (Univ of Edinburgh) and Kitty Meeks (Univ Glasgow) who have been elected to the Young Academy of Scotland.
There are only 126 members from all disciplines. The Academy: provides a platform for able and innovative young entrepreneurs, professionals and academics to develop a coherent and influential voice, and to address the most challenging issues facing society in Scotland and beyond. Jessica and Kitty are using parameterized complexity to exploit the structural properties of networks that describe how cattle and sheep move around Britain, as well as how farms contact each other geographically and via wind movement. Jess is the General Secretary of the Edinburgh Mathematical Society, Kitty currently holds a Royal Society of Edinburgh Personal Research Fellowship at the Univ of Glasgow.
THREE NEW BOOKS!!
(1) Classes of Directed Graphs, Editors: Bang-Jensen, Jørgen and Gutin, Gregory, Springer, 2018.
This book gives a detailed account of the theory of directed graphs from the perspective of important classes of digraphs, with each chapter written by experts on the topic. Authors
include Stephan Kreutzer, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlstrom.
This book provides a comprehensive overview of the latest research in the field. It covers core new results on each of the classes discussed, including chapters on tournaments, planar digraphs, acyclic digraphs, Euler digraphs, graph products, directed width parameters, and algorithms. Explored are structural results as well as algorithms and complexity, including results on fixed parameter tractability. Detailed indices ease navigation while more than 120 open problems and conjectures ensure that readers are immersed in all aspects of the field.
Classes of Directed Graphs provides a valuable reference for graduate students and researchers in computer science, mathematics and operations research. As digraphs are an important modelling tool in other areas of research, this book will be a useful resource to researchers working in bioinformatics, chemoinformatics, sociology, physics, medicine, etc.
(2) Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis. Iris van Rooij, Johan Kwisthout, Todd Wareham, and Mark Blokpoel. Cambridge University Press, 2019.
This book covers both classical and parameterized complexity. It introduces the mathematical concepts and proof techniques that can be used to test one's intuition of (in)tractability. It
describes how these tools can be applied to cognitive modeling to deal with intractability and its ramifications in a systematic way. Aimed at students and researchers in philosophy, cognitive neuroscience, psychology, artificial intelligence, and linguistics who want to build a firm understanding of intractability and its implications in their modeling work, it is an ideal resource.
Advance praise: Computational complexity has long been the elephant in the room in cognitive science. Researchers, including myself, blithely propose models that, if taken literally, would imply the brain can solve computational problems that are known to be intractable. This excellent introduction to both the technical results and their cognitive relevance should alert students and researchers to these pressing questions. Nick Chater -Univ of Warwick.
(3) Kernelization: Theory of Parameterized Preprocessing. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi. Cambridge Univ Press. Anticipated Dec 2018.
Preprocessing, or data reduction, is a standard technique for simplifying and speeding up computation. Written by a team of experts, this book introduces a rapidly developing area of preprocessing analysis known as kernelization. The authors provide an overview of basic methods and important results, with accessible explanations of the most recent advances
such as meta-kernelization, representative sets, polynomial lower bounds, and lossy kernelization. The text covers upper bounds, meta-theorems, lower bounds, and beyond kernelization. The methods are demonstrated through extensive examples using a single data set. Written to be self-contained, the book only requires a basic background in algorithmics and will be of use to professionals, researchers and graduate students in theoretical
computer science, optimization, combinatorics, and related fields.
Advance praise: Kernelization is one of the most important and most practical techniques coming from parameterized complexity. In parameterized complexity, kernelization is the technique of data reduction with a performance guarantee. From humble beginnings in the 1990's it has now blossomed into a deep and broad subject with important applications, and a well-developed theory. Time is right for a monograph on this subject. The authors are some of the leading lights in this area. This is an excellent and well-designed monograph, fully suitable for both graduate students and practitioners to bring them to the state of the art. The authors are to be congratulated for this fine book. Rod Downey, Victoria Univ of Wellington.
Nominate for the EATCS PRESBURGER AWARD for Young Scientists 2019. Deadline: December 31st, 2018. Nominate outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers. Nominatees must be at most 35 years at the time of the deadline of nomination (i.e., for 2019 the date of birth should be in 1983 or later). The 2019 Award Committee consists of Thore Husfeldt (Lund Univ and IT Univ of Copenhagen), Anca Muscholl (LaBRI, Bordeaux) and Jukka Suomela (Aalto, chair).
Nominations, consisting of a two page justification and (links to) the respective papers, as well as supporting letters, should be sent by e-mail to: gro.sctae|drawa-regrubserp#gro.sctae|drawa-regrubserp
The subject line of every nomination should start with Presburger Award 2019, and the message must be received before December 31st, 2018.
The award includes an amount of 1000 Euro and an invitation to ICALP 2019 for a lecture.
Official website: http://www.eatcs.org/index.php/presburger
CONGRATULATIONS Eunjung Kim (Charge de Recherche, CNRS, LAMSADE, Paris Dauphine Univ). Eunjung has been awarded 210,000 Euro by the National Research Agency (ANR) of France for her research project, Algorithms with Small Separations acKnowledged: graphs and linear matroids (ASSK). The theme of this project is small separation phenomena on graphs and linear matroids, emphasizing the applications on algorithm design. The grant duration will be 2019-2022, with a postdoc position available.
CONGRATULATIONS Bart Jansen (Eindhoven Univ of Technology, Netherlands). Bart has received an ERC Starting Grant for his project, REDUCESEARCH: Rigorous Search Space Reduction. The project will develop preprocessing methods that reduce the search space of problem-solving algorithms. See the announcement at https://www.tue.nl/en/our-university/departments/mathematics-and-computer-science/news/erc-starting-grant-for-bart-jansen-simplifying-prior-to-solving/.
CONGRATULATIONS Saket Saurabh (University of Bergen). Saket has been awarded an ERC Consolidator Grant. This is Saket’s second ERC grant; he held an ERC starting grant between 2013-2017. See the announcements at
https://www.uib.no/matnat/122333/han-vil-gjere-big-data-mindre, and
https://www.uib.no/en/matnat/122331/making-sense-big-data. The Department of Informatics celebrated Saket with cake and champagne.
CONGRATULATIONS Mike Fellows AC HFRSNZ MAE, University of Bergen, for being elected to Academia Europaea.The Academia Europaea is an independent learned society and European Union’s Academy of Humanities and Sciences. On the initiative of Royal Society and other National Academies in Europe, the Academia was founded in 1988 as the functioning Europe-wide Academy that encompasses all fields of scholarly inquiry.
CONGRATULATIONS Professor Rod Downey FRSNZ. Rod has been awarded the Rutherford Medal by Royal Society Te Apārangi for his revolutionary research into mathematical logic and computer science.
The Rutherford Medal is the highest honour awarded by the Society for an exceptional contribution to advancing and promoting knowledge for the benefit of New Zealand.
Rod gives a brief comment about parameterized complexity and its usefulness on the website https://royalsociety.org.nz/what-we-do/medals-and-awards/medals-and-awards-news/2018-rutherford-medal-solving-cant-compute-and-is-that-random-sequence-really-random/
Professor Rod Downey, of Victoria University of Wellington, is an internationally recognised logician known for his research into computability—how can mathematical processes be algorithmically implemented either in theory or practice — and the study of randomness, and co-founder of Parameterized Complexity with Mike Fellows.
CONGRATULATIONS to NERODE PRIZE WINNERS Stefan Kratsch and Magnus Wahlström for Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal (ACM Trans. Algorithms 10(4): 20:1-20:15, 2014).
--
CONGRATULATIONS to Marc Roth (Saarland University and Cluster of Excellence (MMCI), Saarbrücken, Germany), Johannes Schmitt (ETH Zürich, Zürich, Switzerland). The 2018 IPEC Program Committee has selected their paper, Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness for the IPEC 2018 Excellent Student Paper Award and for the IPEC 2018 Best Paper Award.
CONGRATULATIONS to Ronald de Haan who was endowed with the honor of participating in the Heidelberg Laureate Forum (HLF). The HLF is a gathering of laureates of some of the most prestigious prizes in mathematics and computer science. Held in Heidelberg, Germany, from September 23-28 2018, the Heidelberg Laureate Forum brings these laureates at the apex of their careers together with 200 high-achieving graduate student and postdoctoral counterparts from around the world. The HLF gives early career researchers an opportunity for interaction that is typically not available within the normal university environment or in their home university department.
CONGRATULATIONS to Gregory Gutin who has been awarded a British pounds 210K grant for 3 years
in access control in info security, where parameterized algorithmics will be used. The project is Analyzing Security-aware Workflows.
Gregory is looking for a postdoc for a 3-year position with a very decent salary (37K pounds a year the 1st year and +2K each consecutive year). The start day is 1st Oct 2018. The topic is parameterized algorithmics applied to access control in info security, but not limited to it. It's a continuation of the previous parameterized algorithmics + access control grant, where Gregory had three PDRAs of which two
quite easily found permanent positions soon afterwards, in UK and France, and one, simply did not want a permanent position yet. Contact: <ku.ca.luhr.sc|nitug#ku.ca.luhr.sc|nitug>
CONGRATULATIONS to Ignasi Sau who defended his Habilitation at LIRMM Université de Montpellier on Parameterized Complexity on Monday 25 June. Reports were from Mike Fellows, Fedor Fomin, Rolf Niedermeier. Examiners were Dimitrios Thilikos, Jean-Claude Bermond, Marc Noy and Gilles Trombetton.
ICALP 2018 satellite workshop: Algorithmic Aspects of Temporal Graphs will be held in Prague on Monday 9 July 2018. In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs will be presented. Some of the key challenges will be highlighted. A participant can register only to the workshop (Monday 9 July), or to both the workshop and the conference (Monday 9 July to Friday 13 July). See https://iuuk.mff.cuni.cz/~icalp2018/registration
ICGT 2018 - 10th International Colloqium on Graph Theory and combinatorics ICGT is a conference created in the honour of C.Berge in 1976 and organized by the French community in Graph Theory every 4-5 years. This 10th edition succeeds the editions of Grenoble in 2014, Orsay in 2010 and Hyères in 2005, and will take place in Lyon from July 9th to 13th 2018. See http://liris.cnrs.fr/~icgt2018/
mail: rf.srnc.siril|8102tcgi#rf.srnc.siril|8102tcgi
Apply for the 2018 Algorithms PhD Students Travel Award. The Algorithms Journal Editor-in-Chief, Henning Fernau announces that the award aims to assist junior researchers to attend an international conference. Deadline to apply is 31 May. The winner will be announced by 15 June. See
http://www.mdpi.com/journal/algorithms/awards.
CONGRATULATIONS!! The paper "Recognizing hyperelliptic graphs in polynomial time",
by Jelco Bodewes and Marieke van der Wegen, and coauthored by Hans Bodlaender and Gunther Cornelissen, has received the Best Student Paper award at WG 2018. Marieke is a PhD student in Utrecht.
CONGRATULATIONS to Prof. Jurik Nesetril, who has received the Donatio Universitatis Carolinae
prize “for his contribution to mathematics and for his leading role in establishing a world-renowned group in discrete mathematics at Charles University”. The prize was given by the rector of the university on the occasion of the 670th anniversary of the establishment of Charles University. It comes with one million CZK support. (https://www.mff.cuni.cz/verejnost/konalo-se/2018-04-nesetril/)
The Parameterized Approximation Algorithms Workshop (PAAW) will take place as a satellite workshop of ICALP 2018 in Prague, Czechia, on Monday July 9th 2018. https://sites.google.com/site/aefeldmann/workshop
Register through the ICALP registration page (early registration deadline is May 31): https://iuuk.mff.cuni.cz/~icalp2018/registration
CONGRATULATIONS TO NERODE PRIZE WINNERS Stefan Kratsch and Magnus Wahlström for
Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. ACM Trans. Algorithms 10(4): 20:1-20:15 (2014)
The search for polynomial kernelization algorithms played a central role in the research on parameterized complexity during the last decade. By now, there are well-developed tools for both positive and negative results in this area. Kratsch and Wahlström were the first to recognize the applicability of the matroidbased machinery (developed earlier by Marx, based on classic results of Lovász) to the compression of NP-hard cut problems. Their work settled the long-standing open problem about the polynomial kernelizability of the Odd Cycle Transversal problem in a beautiful way.
The paper, and its follow-up (Representative Sets and Irrelevant Vertices: New Tools for Kernelization. FOCS 2012), have been very influential and paved the way for several other matroid-based kernelizations, such as those for Vertex Multiway Cut, Above-Guarantee Vertex Cover, and Subset Feedback Vertex Set. Moreover, experiments show
that matroid-based compression is not merely a nice theoretical concept, but also gives relevant practical speedups (Stefan Fafianie, Stefan Kratsch: An Experimental Analysis of a Polynomial Compression for the
Steiner Cycle Problem. SEA 2015: 367-378). For this reason, the Nerode Prize 2018 Committee unanimously decided that the this foundational paper by Kratsch and Wahlström deserves to win the Nerode prize.
PARAMETERIZED COMPLEXITY FOR PRACTICAL COMPUTING (PCPC). Mike Fellows has put the pdf of his Research Council of Norway Toppforsk awarded grant proposal on the Publications page of his personal website: Michael Ralph Fellows <www.mrfellows.net>. The proposal describes the practical computing ecology and introduces new terminology and ideas such as: “The Third Wave of FPT”, “Reverse Kernelization”, “Inductive Gradients”, ”Smooth (Groovy) Kernelization” , "Permissive Turbocharging", and other new, cool ideas. Please cite his proposal for these topics. Citation:
Michael R. Fellows: Norwegian Research Council Toppforsk Proposal, “Parameterized Complexity for Practical Computing” (PCPC). Submitted 2017. Awarded 2018. (Retrieved from http://www.mrfellows.net/publications/)
FPT Workshop in Hobbit-Land, NEW ZEALAND, JULY 25. Parameterized Complexity for Practical Computing
The workshop will be held in Wellington, New Zealand on 25 July 2018. Register by sending an email to Catherine McCartin <zn.ca.yessam|nitraCcM.M.C#zn.ca.yessam|nitraCcM.M.C> or Frances Rosamond <on.biu|dnomasor.secnarf#on.biu|dnomasor.secnarf>. There is no fee for the workshop.
For more information see https://www.cmsc.nz/ftp-workshop/
The main objective of this workshop is to stimulate discussion on the useful purpose of FPT. Topics include turbo-charging heuristics, groovy FPT, reverse kernelization, extremal gradients. Discussion may include how parameterized complexity interacts with operations research, algorithms engineering, machine learning, artificial intelligence, and other areas.
Keynote speaker Mike Fellows will talk about Future Directions of the Field including some of the new directions for which he was awarded the Research Council of Norway Toppforsk Award or about 25 million (See www.mrfellows.net for a copy of the Toppforsk grant proposal).
The original book introducing parameterized complexity written by Downey and Fellows and published in 1999, envisioned the central goal of the program: “to serve the community”.
The main objective of this workshop is to stimulate discussion on outreach to other disciplines or subfields for useful purpose of FPT. To encourage wide participation and discussion, there will be no formal publication of workshop proceedings. Accepted papers will be posted online for the benefit of the workshop participants. Therefore, submission of preliminary work and papers being prepared for other major venues in the field are invited. Participation can be via Skype.
The workshop is informal and broad, and appropriate for PhD, PostDoc and Masters students as well as more senior academics.
Come early and attend CMSC 2018 (See www.cmsc.nz) to explore ways of sharing your research ideas broadly, to non-science audiences.
SOFJA KOVALEVSKAJA AWARD FOR YOUNG RESEARCH TALENTS: APPLICATION DEADLINE: 31 JULY 2018. The Alexander von Humboldt Foundation promotes outstanding talent and best conditions for research. Award winners receive up to €1.65 million each, enabling them to spend five years establishing and heading their own research groups at a research institution in Germany.
Junior academics of all disciplines from abroad with outstanding qualifications, who completed their doctorates within the last six years, are eligible to apply for the Sofja Kovalevskaja Award. Applications may also be submitted on completion of doctoral studies. Six awards are scheduled to be granted.
Visit www.humboldt-foundation.de/skp_en [2] for further information and a link to the online application package. If you have any questions about the Sofja Kovalevskaja Award or would
like individual guidance, please contact us at ed.hva|ofni#ed.hva|ofni.
VIDEO COMPETITION at IJCAI 2018, part of the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence the premier international gathering of researchers in AI! Conference is in Stockholm July 9-19. Submission Deadline: May 5, 2018.
Competition description: A wide range of videos related to artificial intelligence can be submitted to the competition. The topic of a video might, for example, be a general or specific area of AI, the work of a particular researcher or group (yourselves or others), or a concrete application that depends on one or several AI techniques and that may be based entirely on software or partly on hardware. A video may concern work with different levels of maturity: you can introduce something new and interesting, describing known but ongoing research, or summarize a mature area or application, showing its impact on society. The intended audience of a video can be students learning about a topic in a classroom, researchers interested in learning more about subfields outside their own, the general public or the media.
DEADLINE EXTENDED to 30 March. ICGT 2018 - 10th International Colloqium on Graph Theory. ICGT is a conference created in the honour of C.Berge in 1976 and organized by the French community in Graph Theory every 4-5 years. This 10th edition will take place in Lyon from 9—13 July 2018.
http://liris.cnrs.fr/~icgt2018/
mail: srnc.siril|8102tcgi#srnc.siril|8102tcgi
FPT Data Wrangling for Social Good (Wellington, New Zealand, July 25, 2018.
This FPT workshop immediately follows the Creative Mathematical Sciences Communication (CMSC 2018)
conference which will be held 21-23 July in Wellington. Come for both. For details contact organizers Catherine McCartin (zn.ca.yessam|nitraccm.m.c#zn.ca.yessam|nitraccm.m.c) and Peter Shaw (zn.ca.yessam|wahs.p#zn.ca.yessam|wahs.p), both at Massey Univ.
4th Creative Mathematical Sciences Communication conference (CMSC2018). Wellington, NZ, 21—23 July.
(Website is http://www.cmsc.nz). Join scientists, researchers, teachers, and artists in developing new ways of communicating mathematical and computational thinking. Stay for the FPT workshop immediately following.
The 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) will be part of ALGO 2018 and takes place 22-24 August 2018, in Helsinki, Finland.
IMPORTANT DATES: Note that the submission deadline is earlier this year. Title and short abstract
deadline: May 14, 23:59 AoE Full paper submission deadline: May 17, 23:59 AoE, Notification: July 1.
AWARDS: The Program Committee may award one or more Best Paper Award(s) and Best Student Paper
Award(s). Advise the Program Committee if you are submitting for a Best Student Paper Award. 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 if there is one nonstudent co-author that confirms that a clear majority of conceptual work on the paper was done by the student co-author(s). It is expected that a student gives a presentation
at the conference.
SPECIAL EVENTS
NERODE PRIZE: An invited talk will be given by the 2018 EATCS-IPEC Nerode Prize winner.
TUTORIAL: Radu Curticapean will give an invited tutorial on Counting Problems in Parameterized Complexity.
PACE: There will be a session presenting the results of the 3rd Parameterized Algorithms and Computational Experiments Challenge (PACE 2018).
Congratulations to Matthias Mnich (Maastricht Univ, Universitat Bonn) who has received a personal grant of 578.000 Euro from DFG - Deutsche Forschungsgemeinschaft for his project Multivariate Algorithms for Scheduling Problems. Dr. Mnich is also directing Kernelization for Big Data, a DFG project.
The February FPT Newsletter is on the Newsletter page of this website. Editors Frances Rosamond (Univ Bergen) on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF and Valia Mitsou (Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv.
Announcements of awards and prizes, graduates, new jobs, and wonderful research. This newsletter features an article by PACE prize-winner Hisao Tamaki (Meiji University, JP) on Positive-instance
driven dynamic programming for treewidth, and an article on Erdos-Posa property of chordless cycles and its applications by Eun Jung Kim (Universite Paris-Dauphine) and O-joung Kwon (Incheon National University).
CALL FOR PAPERS: Parameterized Approximation Algorithms Workshop (PAAW) will take place
as a satellite workshop of ICALP 2018 in Prague, Czechia, on Monday July 9th 2018.
https://sites.google.com/site/aefeldmann/workshop
Topics of interest
- Parameterized approximation algorithms
- Lossy kernelization
- Parameterized inapproximability
- Fine-grained complexity of approximation
- Efficient polynomial-time approximation schemes
Contributed talks: If you would like to contribute a talk at this workshop, please send an email with subject "PAAW talk" to "feldmann.a.eatgmail.com" containing the title and an abstract, no later than Friday April 20th. Both talks on already published as well as yet unpublished results on the above listed
topics are welcome. There will not be any published proceedings for this workshop.
Important dates
Submission deadline: Friday April 20th, 2018
Notification: Friday May 18th, 2018
Early registration deadline: Thursday May 31, 2018
Workshop: Monday July 9th, 2018
Registration:To participate please register through the ICALP registration page.
Congratulations to Michael Fellows. We are pleased to announce that the Research Council of Norway has awarded a Toppforsk grant of about NOK 25 million for his project, Parameterized Complexity for Practical Computing. The funding scheme supports “scientific quality at the forefront of international research; boldness in scientific thinking and innovation”.
Congratulations to Faisal N. Abu-Khzam (Lebanese American Univ) for his project Efficient Algorithms for repairing quality in dynamic networks. The grant should cover 10 research visits, over two years, between LAU and University of Paris-Dauphine. His partners at Dauphine are Joyce El-Haddad and Cristina Bazgan. The project is funded by CEDRE, the Hubert Curien Partnership (PHC) Franco-Lebanese. It is implemented in France by the Ministry of Europe and Foreign Affairs (MEAE) and the Ministry of Higher Education, Research and Innovation (MESRI). In Lebanon, by the Ministry of Education and Higher Education.
PACE 2018: Coders— prizes & travel awards
Teams or individuals are invited to compete in PACE 2018, the Parameterized Algorithms and Computational Experiments Challenge. Investigate the practical applicability of algorithmic ideas of multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms.
Through the generous sponsorship of NETWORKS (http://thenetworkcenter.nl/ ), an NWO Gravitation project of the Univ of Amsterdam, Eindhoven Univ of Technology, Leiden Univ, and the Center for Mathematics and Computer Science (CWI), we announce 4000 euros that will be divided into prizes and travel awards for participants.
The challenge consists of three tracks on the Steiner Tree problem. Detailed instructions about the three tracks, their rules, the instance sets, and the input and output formats: Challenge https://pacechallenge.wordpress.com/pace-2018/
Register here: https://docs.google.com/forms/d/e/1FAIpQLScHH6lNpUYwLT6GDVMO9ik0s9iwhQTRbxnaJED1wdZOWBtJRg/viewform .
Download the public instances on the PACE challenge website and start your implementation.
Test your code on this platform now: https://pacechallenge.wordpress.com/2017/12/12/optil-io/ .
TIMELINE:
May 1st, 2018: Submission of final program
May 10th, 2018: Result are communicated to participants
August 20-24 2018: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2018) in Helsinki
Congratulations to Rod Downey (Victoria University of Wellington, NZ) who will give the Gödel Lecture at The Logic Colloquium 2018, the annual European summer meeting of the Association of Symbolic Logic (ASL), that will be held during July 23—28, 2018 at the University of Udine, Italy.
Congratulations to Rod also for winning the 2016 Shoenfield Prize for his book with Denis Hirschfeldt: Algorithmic randomness and complexity (Theory and Applications of Computability, Springer-Verlage New York, 2010).
CALL FOR NOMINATIONS — EATCS-IPEC Nerode Prize — Due March 1, 2018
The Nerode Prize is an annual prize for outstanding work in multivariate algorithmics and parameterized complexity, published in a recognized journal by an individual or a team of authors. Please think of any past work in this area that deserves to be recognized by this prize, and send your nominations.
Nominations should contain a brief summary of the technical content of the nominated paper and a brief
explanation of its significance. Send copies to the members of the committee. The Subject line of the nomination E-mail should contain the group of words "Nerode Prize Nomination". Deadline is March 1, 2018.
COMMITTEE: Daniel Marx <uh.emb.sc|xramd#uh.emb.sc|xramd> Award Committee Chair (Hungarian Academy of Sciences),
Jianer Chen <ude.umat.esc|nehc#ude.umat.esc|nehc> (Texas A&M), Hans L. Bodlaender <ln.uu|rednealdob.l.h#ln.uu|rednealdob.l.h> (Utrecht University).
NEWS-Now send your graduation information, grant, new job, book, workshop, submissions, announcements or other news to be included in the next FPT Newsletter. Send to Editors Frances Rosamond on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF or Valia Mitsou rf.srnc.siril|uostim#rf.srnc.siril|uostim.
Congratulations to Anil Nerode on his 85th birthday, which is being celebrated at the Symposium on Logical Foundations Of Computer Science (LFCS) in Deerfield Beach, Florida. Anil especially invited Mike Fellows and Frances Rosamond (Anil was Fran’s advisor at Cornell), and Mike will give the opening plenary on “The Evolution and Future of Parameterized Complexity”.
Jianer Chen writes: Submission for FAW 2018 is December 29, 2017. The EasyChair submission server is available at
https://easychair.org/conferences/?conf=faw2018.
The 12th International Frontiers of Algorithmics Workshop will be held on May 8-10, 2018 at Guangzhou, Guangdong Province, China (www.itcs.shufe.edu.cn/FAW2018/contact.html.)
SOCIAL CHOICE CONFERENCE—LIVE, ONLINE NOW.
Online herehttp://events.iitgn.ac.in/2017/comsoc/
Where the lectures are being broadcast live.
We started a day late because Edith's flight was re-routed, so only the
introductory lectures have finished so far, and about 10+ hours are coming
up still. IIT-Gandhinagar with Edith Elkind and Neeldhara Misra.
Lorentz Center workshop on Fixed-Parameter Computational Geometry II, taking place May 14-18, 2018. Contact organizers for invitation: Mark de Berg, Hans Bodlaender, Benjamin Burton and Christian Knauer.
EATCS Deadlines for award nominations:
EATCS Award 2018 <http://eatcs.org/index.php/eatcs-award> : December 31, 2017
Presburger Award 2018 <http://eatcs.org/index.php/presburger> : December 31, 2017
Eatcs Fellows 2018 <http://eatcs.org/index.php/eatcs-fellows> : December 31, 2017
EATCS Distinguished Dissertation Award 2017 <http://eatcs.org/index.php/dissertation-award> : December 31, 2017
More information can be found at http://www.eatcs.org/index.php/eatcs-awards
COMPUTATIONAL SOCIAL CHOICE course at the Indian Institute of Technology Gandhinagar from 4—8 December 2017 with speaker Prof. Edith Elkind (Oxford). Contact Neeldhara Misra.
Announcing PACE 2018, the Parameterized Algorithms and Computational Experiments Challenge. PACE 2016 and PACE 2017 have been hugely successful (official reports are here https://pacechallenge.files.wordpress.com/2016/06/lipics-ipec-2017-30.pdf). The goal of PACE is to investigate the practical applicability of algorithmic ideas studied and developed in multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms. The challenge this year consists of three tracks on the Steiner Tree problem.
Given an undirected edge-weighted graph G and a subset T (terminals) of its vertices, find a subgraph of G spanning T with the smallest total edge-weight.
TRACK 1 (Exact with few terminals)
You have 30 minutes per instance. Win by solving more instances than the other participants.
In all the instances, there are only a few terminals.
TRACK 2 (Exact with low treewidth)
You have 30 minutes per instance. Win by solving more instances than the other participants.
In this track only, the instances come with a tree decomposition and the treewidth is low.
TRACK 3 (Heuristic)
Here the instances are significantly larger, have many terminals, and high treewidth, but you are not expected to find an optimum solution. You still have 30 minutes per instance. Win by finding Steiner trees of smaller weight than the other participants. We will rank by average approximation ratio.
Detailed instructions about the three tracks, their rules, the instance sets, and the input and output formats: https://pacechallenge.wordpress.com/pace-2018/
You can already register for the challenge: https://docs.google.com/forms/d/e/1FAIpQLScHH6lNpUYwLT6GDVMO9ik0s9iwhQTRbxnaJED1wdZOWBtJRg/viewform .
You can also download the public instances on the PACE challenge website and start your implementation. We cooperate with the platform optil.io (https://www.optil.io/optilion/). In a short while, you will be able to run your code on this platform. We will let you know when it is ready and how to proceed.
TIMELINE:
November 14th, 2017: Announcement of the challenge
May 1st, 2018: Submission of final program
May 10th, 2018: Result are communicated to participants
August 20-24 2018: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2018) in Helsinki
PROGRAM COMMITTEE:
Track 1, 2, 3:
- Édouard Bonnet (Middlesex University, London)
- Florian Sikora (Paris-Dauphine University)
STEERING COMMITTEE:
- Holger Dell (Saarland University and Cluster of Excellence, MMCI)
- Bart M. P. Jansen (chair) (Eindhoven University of Technology)
- Thore Husfeldt (ITU Copenhagen and Lund University)
- Petteri Kaski (Aalto University)
- Christian Komusiewicz (Friedrich-Schiller-University Jena)
- Frances A. Rosamond (University of Bergen)
Best of luck with your code!
The PACE Committees
CONGRATULATIONS, Tim Bell!! The 2018 SIGCSE Award for Outstanding Contribution to Computer Science Education has been awarded to Professor Tim Bell, University of Canterbury, New Zealand. Tim and Mike Fellows and Ian Witten authored "Computer Science Unplugged" (csunplugged.org). Computational thinking has been infused into schools around the world as a result. Tim is a Keynote Speaker at the Creative Mathematical Sciences Communication Conference (CMSC4) in New Zealand 21-24 July 2018. All welcome. There will be an FPT Workshop adjacent to CMSC4. See cmsc.nz
CONGRATULATIONS!! There are 15 Parameterized Complexity papers at SODA 2018. Eight of them are from the University of Bergen.
PARAMETERIZED COMPLEXITY WEEK AT IMSC, CHENNAI, October 24—26. In honor of wedding of MSR. Organized by Venkatesh Raman. See t www.imsc.res.in/~vraman/pcweek.pdf
schedule for PC Week
If you are looking for a position in the UK, then look on the page www.jobs.ac.uk. The UK is attending to another RQF (Research Quality Framework) and they are looking to hire researchers with high-profile, quality papers, ability to recruit students, grants, and impact—it helps to have experience in programming competitions (PACE, see https://pacechallenge.wordpress.com) and other outreach.
Congratulations to Marc Roth (Saarland Univ) who was awarded the 2017 ESA Best Student Paper Award for Counting restricted homomorphisms via Möbius inversion over matroid lattices.
Congratulations to Gregory Gutin, Professor of Computer Science, Royal Holloway, University of London who has been elected to the Academia Europaea as a Member of the Informatics Section. See http://www.ae-info.org/ae/Member/Gutin_Gregory
Congratulations to Matthias Bentert,Till Fluschnik, André Nichterlein and Rolf Niedermeier for winning Best Student Paper Award at the 21st Symposium on Fundamentals of Computation Theory (FCT '17) for their paper, Parameterized Aspects of Triangle Enumeration. They also won ALGOSENSORS 2017 Best Paper Award. Great teamwork.
Optimisation Summer School in Australia, January 14th to 19th 2018 (http://tinyurl.com/optschool). Spend a week by the beach learning about the latest optimisation technologies. The school will focus on solving large scale combinatorial optimisation problems in practice. The school is intended for undergraduate students (3rd year or later), masters or early stage PhD students. Every undergraduate participant will be assigned an individual mentor. Topics covered include: introduction to constraint programming, modelling, integer programming, parameterized complexity techniques, column generation, vehicle routing, scheduling, evolutionary methods and research skills.Organizer Prof. Toby Walsh, UNSW and Data61.
Slides from the 2017 IPEC Business Meeting Report (by Stefan Kratsch), PC Chairs Report (by Daniel Lokshtanov and Naomi Nishimura, and Publicity Report (Frances Rosamond) are available on the IPEC page. There will be a brief summary in the next newsletter. Thank you to incoming IPEC Steering Committee members Christophe Paul, Michał Pilipczuk, and Magnus Wahlström. Thank you to those outgoing this year for your valuable service: Thore Husfeldt, Iyad Kanj and Gerhard Woeginger.
Congratulations to Martin Aleksandrov and Toby Walsh for their paper: Expected Outcomes and Manipulations in Online Fair Division, which won Best Paper Prize at the 40th German Conference on Artificial Intelligence (KI'2017). This is the second time Martin has won a best paper award during his PhD.
Congratulations to Marek Cygan, Lukasz Kowalik, Arkadiusz Socala who won the ESA Best Paper Award Track A for their paper, Improving TSP tours using dynamic programming over tree decompositions.
Congratulations to Matthias Bentert, René van Bevern, André Nichterlein, and Rolf Niedermeier who won the ALGOSENSORS Best Paper Award Algorithms Track at ALGO for their paper, Parameterized algorithms for power-efficient connected symmetric wireless sensor networks.
The EATCS-IPEC Nerode Prize 2017 for outstanding papers in the area of multivariate algorithmics has been awarded to Fedor V. Fomin (Univ Bergen), Fabrizio Grandoni (IDSIA, Univ Lugano), and Dieter Kratsch (Univ Lorraine - Metz) for their paper: A measure & conquer approach for the analysis of exact algorithms (Journal of the ACM 65 (5): Article 25, 2009). Congratulations!
Congratulations to all PACE 2017 winning teams and participants. The PACE 2018 Steering Committee Chair is Bart Jansen. The PACE 2018 PCs are Édouard Bonnet and Florian Sikora. Thank you to our PACE sponsor Networks. Photos thanks to Rudolf Fleischer are on facebook (@MikeFellowsFPT). Lightswords curtesy of Frances Rosamond. Sign up for the PACE Newsletter at pacechallenge.wordpress.com.
Track A: Optimal Tree Decomposition
1. Lukas Larisch (King-Abdullah Univ Science and Engineering), Felix Salfelder (Univ Leeds)
2. Hiromu Ohtsuka, Hisao Tamaki (Meiji Univ)
3. Max Bannach (Univ Lübeck), Sebastian Berndt (Univ Lübeck), Thorsten Ehlers (Univ Kiel)
Track A: Heuristic Tree Decomposition
1. Keitaro Makii, Hiromu Ohtsuka, Takuto Sato, Hisao Tamaki (Meiji Univ)
2. Ben Strasser (Karlsruhe Institute of Technology)
3. Michael Abseher, Nysret Musliu, Stefan Woltran (TU Wien, Institute of Information Systems)
Track A Honors
4. Max Bannach (Univ Lübeck), Sebastian Berndt (Univ Lübeck), Thorsten Ehlers (Univ Kiel)
5. Philippe Jégou, Hanan Kanso, Cyril Terrioux (Aix-Marseille Université, LSIS)
6. Lukas Larisch (King-Abdullah Univ Science and Engineering), Felix Salfelder (Univ Leeds)
Track B: Minimum Fill-In
1. Yasuaki Kobayashi (Kyoto Univ) and Hisao Tamaki (Meiji Univ)
2. Jeremias Berg, Matti Järvisalo, Tuukka Korhonen (Univ Helsinki).
3. Édouard Bonnet (UnivParis-Dauphine), R.B. Sandeep (Hungarian Academy of Sciences), Florian
Sikora (Univ Paris-Dauphine)
Track B Honors
4. Anders Wind Steffensen, Mikael Lindemann (IT Univ Copenhagen)
5. Kaustubh Joglekar, Akshay Kamble, Rajesh Pandian (Indian Institute Of Technology, Madras)
6. Saket Saurabh (Univ Bergen), Prafullkumar Tale (Institute of Mathematical Sciences, Chennai)
7. Mani Ghahremani (Univ Portsmouth)
8. Frederik Madsen, Mikkel Gaub, Malthe Kirkbro (IT Univ Copenhagen).
Congratulations Radu Curticapean (Hungarian Academy of Sciences), Holger Dell (Saarland Univ), Fedor Fomin (Univ Bergen), Leslie Ann Goldberg (Univ Oxford) and John Lapinskas (Univ Oxford) who have won IPEC 2017 Best Paper Award for A Fixed-Parameter Perspective on #BIS. A summary of their award-winning paper will appear in the next newsletter.
Congratulations Astrid Pieterse and Bart M. P. Jansen (Eindhoven Univ of Technology) for winning the IPEC2017 Excellent Student Paper Award with Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials. A summary of their award-winning paper will appear in the next newsletter.
SEEKING CHALLENGE PROBLEMS. Send your suggestion for the 2018 PACE Challenge problems to Holger Dell <moc.liamg|lled.regloh#moc.liamg|lled.regloh>, 'Christian Komusiewicz' <ed.anej-inu|zciweisumok.naitsirhc#ed.anej-inu|zciweisumok.naitsirhc>, "Bart M. P. Jansen" <moc.liamg|nesnajpmb#moc.liamg|nesnajpmb>. The 2017 PACE CHALLENGE WINNERS will be announced at the PACE meeting immediately following the IPEC Business meeting, and in the same room.
Congratulations!! Hisao Tamaki (Meiji University) has won the best ESA Track B paper award for his paper accompanying his PACE17 submission. The title of his paper is Positive-instance driven dynamic programming for treewidth. He says this work would not have happened without the motivation of the PACE challenge.
The 2017 June, Vol 13, no 2 Parameterized Complexity Newsletter is on the newsletter page. Co-editors: Valia Mitsou (LIRIS, CNRS Univ Lyon 1) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv and and Frances Rosamond (Univ of Bergen) on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF. This newsletter contains announcements of many awards, prizes, best papers and graduates. There is an insightful article by Fahad Panolan on Lossy Kernelization. Ronald de Haan, winner of the Dutch E. W. Beth Dissertation Prize, discusses a new direction of FPT SAT Encodings. Workshops and events are announced. Enjoy!
Tutorial: An Introduction to Parameterized Complexity with Applications in Algorithmic Decision Theory.italic text ADT 2017 Tutorial and Doctoral Consortium day: October 24, 2017. Serge Gaspers (School of Computer Science and Engineering, UNSW Sydney and Data61, CSIRO, Australia).
5th Intl Conf on Algorithmic Decision Theory (ADT 2017)
Luxembourg, 25—27 October 2017
http://sma.uni.lu/adt2017
Early registration: before August 31
The ADT 2017 seeks to bring together researchers and practitioners coming from diverse areas such as Artificial Intelligence, Database Systems, Operations Research, Discrete Mathematics, Theoretical Computer Science, Decision Theory, Game Theory, Multiagent Systems, Computational Social Choice, Argumentation Theory, and Multiple Criteria Decision Aiding in order to improve the theory and practice of modern decision support. Some of the scientific challenges facing the Algorithmic Decision Theory (ADT) community include big preference data, combinatorial structures, partial and/or uncertain information, distributed decision making, and large user bases. Such challenges occur in real-world decision making in domains like electronic commerce, recommender systems, argumentation tools, network optimization (communication, transport, energy), risk assessment and management, and e-government.
Congratulations to Ronald de Haan. The Association for Logic, Language and Information (FoLLI) has awarded the E. W. Beth Dissertation Prize, named in honor of the Dutch mathematician Evert Willem Beth to Ronald for his outstanding dissertation, Parameterized Complexity in the Polynomial Hierarchy, Technical University of Vienna. See Ronald's article in the June 2017 Parameterized Complexity Newsletter.
There is a lot happening in Australia this summer:
1. Computational & Algorithmic Topology Workshop (CATS), The Univ of Sydney, 27 June – 1 July 2017. Serge Gaspers will give an introductory lecture on parameterized complexity.
2. Computational Geometry Week (CG Week 2017), the premier international forum for advances in computational geometry and its many applications. Univ of Queensland, Brisbane, July 4–7. Benjamin Burton, local organizer.
3. The 28th International Workshop on Combinatorial Algorithms (IWOCA2017), Newcastle, July 17–21. Special memorial to Mirka Miller.
4. ICML and UAI in Sydney, August 6–15.
5. The big IJCAI / SAT / CP / ICLP event in Melbourne, August 19 – September 1.
Recent Advances in Parameterized Complexity (rapctelaviv.weebly.com). The event will be held on December 3-7, 2017, at Tel Aviv, Israel.
The purpose of Recent Advances in Parameterized Complexity is twofold. First, the event would present an overview of several recent, exciting advances in the field of Parameterized Complexity. Second, to attract new researchers to work on topics in this field of research, the program would also consist of a preparatory school at the level of an introductory course. We thus invite both graduate students and established researchers to participate in Recent Advances in Parameterized Complexity. For more details, see rapctelaviv.weebly.com.
PACE deadline extended until May 25. Thanks to the cooperation with OPTIL.io (http://www.optil.io ), the notification will still be sent out June 1. Good luck and fun to all participants in the remaining weeks. We look forward to seeing you at IPEC, where there will be a special surprise for all participants.
New positions have been announced on the JOBS PAGE.
STOC 2017 BEST PAPER AWARD FPT results have been selected for a STOC2017 BEST PAPER AWARD: Deciding Parity Games in Quasipolynomial Time by Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephen. See https://www.comp.nus.edu.sg/~fstephan/publications.html, publication number 181. See also the article in the Vol12 (2) November 2016 Parameterized Complexity Newsletter.
CONGRATULATIONS STOC17 PAPERS:
Faster Space-Efficient algorithms for Subset Sum and k-Sum by Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas.
Homomorphisms Are a Good Basis for Counting Small Subgraphs by Radu Curticapean, Holger Dell, Dániel Marx.
Lossy Kernelization by Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Ramanujan Sridharan.
SEE FPT PAPERS ONLINE here and PAPERS IN CONFERENCES here. Many thanks to Bart Jansen for collecting.
PARAMETERIZED COMPLEXITY SUMMER SCHOOL The 3rd Parameterized Complexity Summer School will be held in Vienna, Austria, from 1 to 3 September 2017 (Friday-Sunday) co-located with ALGO 2017 and will take place in the same venue. See https://algo2017.ac.tuwien.ac.at/pcss/
PACE UPDATE: Submission is possible from now until May 1 for both tracks of PACE 2017. We are happy to announce that PACE 2017 will cooperate with OPTIL.io to handle the submission process and the evaluation of submissions. OPTIL.io is a website for organizing programming challenges for optimization problems, created and maintained by the Institute of Computing Science of Poznan University of Technology.
CALL FOR PAPERS: IPEC 2017 Vienna, Austria 4—8 September 2017.
Important Dates
Abstract Submission: June 25, 2017
Paper Submission: June 28, 2017
Notification of acceptance: July 25, 2017
Symposium: September 6-8, 2017
Excellent Student Paper Award eligibility: at most one author has received a PhD degree before the paper submission deadline. The students' contributions must be substantial, and a student must give the presentation at the conference. IMPORTANT Please identify if you are submitting a Student Paper. There will also be Best Paper Award (not necessarily student).
Stefan Szeider would like to bring to the attention of the Parameterized Complexity community the call for the 8th Vienna Research Groups for Young Investigators. The level of excellence is similar to an ERC starting grant, but the setup is slightly different. A crossover between mathematics and CS might be an interesting combination for the call. A successful candidate has good chances for negotiating a permanent contract with TU Vienna. Submit proposals by July 13, 2017. All interested parties are cordially invited to an open Proposers’ Day on April 6, 2017. Detailed information is available online (www.wwtf.at).
ARE YOU READY FOR A CHALLENGE? See https://pacechallenge.wordpress.com/pace-2017
TRACK A (Treewidth Challenges)
1) Compute a tree-decomposition of minimum width. You have 30 minutes per instance. Win by solving more instances than the other participants.
2) Compute some tree-decomposition. You have 30 minutes per instance. Win by printing solutions of smaller width than the other participants.
Detailed instructions and fresh instance sets:
https://pacechallenge.wordpress.com/pace-2017/track-a-treewidth/
TRACK B (Minimum Fill-In Challenge)
Given an undirected graph G, compute a smallest set of edges E such that adding E to G results in a chordal graph. You have 30 minutes per instance. Win by solving more instances than the other participants.
Detailed instructions and an instance set:
https://pacechallenge.wordpress.com/pace-2017/track-b-minimum-fill-in/
Congratulations to George Mertzios (Durham University) who has received an EPSRC award (the UK research funding body) for "Algorithmic Aspects of Temporal Graphs". The project topic is algorithms and complexity for problems in temporal (i.e. dynamically changing) graphs. Apply for a 3-year full-time PostDoc position (start date is April 2017, or soon thereafter; there is some flexibility on the starting date). The salary will be £32000 - £35000 p.a. Candidates with a good knowledge of parameterized complexity and algorithms are encouraged to apply. More details about the project can be found here: http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/P020372/1. For inquires about the project and the application process, please contact George Mertzios (ku.ca.mahrud|soiztrem.egroeg#ku.ca.mahrud|soiztrem.egroeg; see also http://community.dur.ac.uk/george.mertzios/)
The The February 2017 Parameterized Complexity Newsletter is on the wiki newsletter page here. It lists awards and prizes, graduates, new jobs, and wonderful research. Michael Wehar gives a new look at fine-grained FPT. IPEC Excellent Paper winner Marcin Wrochna writes about “FPT inside P”. NWO award winner Johan Kwisthout discusses a framework for Fixed-error Randomized Tractability. Australia's Chris Wallace Award for a notable CS breakthrough has been awarded to Haris Azis. Haris writes about cake-cutting and suggests open problems. Enjoy!
Congratulations to Eunjung Kim (Charge de Recherche CNRS (Junior Researcher) LAMSADE, Univ
Dauphine) who has been awarded the Bronze Medal by the National Center for Scientific Research (CNRS). The Medal is intended to recognize and encourage an already productive French junior researcher who is a well-committed and promising specialist in computer science.
ALGORITHMS—TRAVEL AWARD
Prof. Dr. Henning Fernau, Editor-in-Chief of Algorithms announces a competition for an annual Travel Award sponsored by Algorithms. The Travel Award consists of 800 Swiss Francs and will be granted to a PhD student in the area of algorithms and their applications, to attend a conference in 2017. Applications until 31 March 2017.
NERODE PRIZE DEADLINE MARCH 1, 2017 The EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics.
ELIGIBILITY: research paper or series of research papers by a single author or by a team of authors published in a recognized refereed journal. The year of publication should be at least two years and at most ten years before the year of the award nomination. 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.
NOMINATE: Send an email to Award Committee Chair containing a brief summary of the technical content of each nominated paper and a brief explanation of its significance. Send copies to the members of the committee. The Subject line of the nomination E-mail should contain the group of words "Nerode Prize Nomination".
SEND EMAIL
David Eppstein <ude.icu|nietsppe#ude.icu|nietsppe> Award Committee Chair (University of California, Irvine)
Daniel Marx <uh.emb.sc|xramd#uh.emb.sc|xramd> (Hungarian Academy of Sciences)
Jianer Chen <ude.umat.esc|nehc#ude.umat.esc|nehc> (Texas A&M)
Recent Advances in Algorithms: International Computer Science Student School
May 22–26, 2017, St. Petersburg, Russia. http://raa-school.org
IMPORTANT DATES
Application: February 10, 2017
Notification: February 20, 2017
Registration: February 27, 2017
AIM OF THE SCHOOL The school offers the unique opportunity to learn about recent breakthroughs in several domains of algorithms: from classical areas like network algorithms and longest paths in graphs to recently emerged areas like streaming
algorithms and algorithms for high dimensional data. The lectures will be taught by the leading researchers in these areas. Each of the tutorials will provide an introduction to the area and gradually bring to the current research frontiers.
The primarily audience consists of PhD students interested in Algorithms. Bright master students, postdocs, young researchers and even faculty are also very welcome.
LECTURERS
Michael Kapralov (EPFL) Streaming Algorithms
Aleksander Mądry (MIT) Graph Algorithms and Continuous Optimization
Ilya Razenshteyn (MIT) Algorithms for High-Dimensional Data
Saket Saurabh (IMSc) Longest Paths in Graphs: Parameterized Algorithms
VENUE The school is hosted by St. Petersburg Department of V.A. Steklov Institute of Mathematics of the Russian Academy of Sciences which is located in the very center of St. Petersburg.
CONFERENCES. Consider submitting.
FAW 2017: 11th International Frontiers of Algorithmics Workshop will be held on June 23-25, 2017 at Chengdu, Sichuan, China. Submission deadline: February 3.
TCS 2017 : Topics in Theoretical Computer Science will be held September 12—14 at Institute for Research in Fundamental Sciences (IPM), Tehran, Iran. Abstract Registration: 1 May. Submission Deadline: 8 May
See http://community.dur.ac.uk/tom.friedetzky/conf.html
Congratulations to Johan Kwisthout (Donders Institute for Brain, Cognition and Behaviour) who has received an NWO EW Physical Sciences Division TOP grant for the project Parameterized Complexity of Approximate Bayesian Inference. The 217,000 Euro grant is for four years (April 2017-March 2021). Applications for a PhD candidate on a fully paid fellowship for four years plus additional costs are being accepted.
Congratulations to Professor Fedor Fomin (Univ Bergen) who has received a Norwegian Research Council (NFR) grant for Multivariate Algorithms: New Domains and Paradigms. There will be 2 postdoctoral and 1 PhD position. Please apply.
There has been a very powerful cyclone in Chennai, with everyone being cut off from internet for several days. Fedor has recently returned from Chennai and reports it an experience! We send all our Chennai friends the very best wishes.
Congratulations to Saket Saurabh (Univ of Bergen) who is now Associate Editor of JCSS. Mike Fellows (Univ Bergen) has been appointed to the Editorial Board of JCSS. Congratulations to Bart Jansen (Eindhoven Univ) who is now Associate Editor of TALG. These positions embody an enormous amount of volunteer work and responsibility. Please help these new editors by reviewing promptly and with good will. They are contributing mightily to the PC community and to TCS largely.
Congratulations to Professor Toby Walsh (UNSW School of Computer Science and
Engineering) who has won the NSW Premier's Award for Excellence in Engineering and Information and Communications Technologies. Toby is a global leader in AI and one of the top five most-cited computer scientists in Australia. He builds computer programs for important tasks, such as optimising the efficiency of distributing donated food to charities. He researches the interface between optimisation (making better decisions), social choice (taking account of agents’ preferences), and game theory (taking account of self-interested agents).
The Parameterized Complexity Newsletter, Vol 12, no 2, Nov 2016 is on the wiki. Read announcements of many awards, prizes and graduates. There is an insightful article by Gregory Gutin (Royal Holloway, Univ London) on FPT algorithms beating MIP Solver, and an article by Michal Wlodarczyk (Univ Warsaw) on New Algebraic tools for Treewidth-motivated Convolutions. We also announce breakthrough results in parity games. Please welcome Valia Mitsou (Hungarian Academy of Sciences) as new co-editor of the newsletter.
The 2017 Parameterized Algorithms and Computational Experiments Challenge (PACE): consists of two separate tracks. See: https://pacechallenge.wordpress.com/pace-2017https://pacechallenge.wordpress.com/pace-2017 for details.
TRACK A (Treewidth Challenges)
1) Compute a tree-decomposition of minimum width. You have 30 minutes per instance. Win by solving more instances than the other participants.
2) Compute some tree-decomposition. You have 30 minutes per instance. Win by printing solutions of smaller width than the other participants.
TRACK B (Minimum Fill-In Challenge)
Given an undirected graph G, compute a smallest set of edges E such that adding E to G results in a chordal graph. You have 30 minutes per instance. Win by solving more instances than the other participants.
TIMELINE
December 1st, 2016: Announcement of the challenges
March 1st, 2017: Submission of preliminary version for bugfixing and leaderboard
May 1st, 2017: Submission of final version
June 1st, 2017: Announcement of the results
September 4-8, 2017: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2017) in Vienna
PROGRAM COMMITTEE
Track A (tree width):
- Holger Dell (Saarland University and Cluster of Excellence (MMCI))
Track B (min fill-in):
- Christian Komusiewicz (chair) (Friedrich-Schiller-University Jena)
- Nimrod Talmon (Weizmann Institute of Science)
- Mathias Weller (Laboratory of Informatics, Robotics, and Microelectronics of Montpellier (LIRMM))
STEERING COMMITTEE
- Holger Dell (Saarland University and Cluster of Excellence, MMCI)
- Bart M. P. Jansen (Eindhoven University of Technology)
- Thore Husfeldt (ITU Copenhagen and Lund University)
- Petteri Kaski (Aalto University)
- Christian Komusiewicz (Friedrich-Schiller-University Jena)
- Frances A. Rosamond (chair) (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF, University of Bergen)
Workshop: The Sydney Algorithms Workshop (SAW 2016)
Where: Sydney (Australia).
When: 6-9 December 2016.
Organizers: Joachim Gudmundsson, Serge Gaspers, Stefan Rümmele, and Julián Mestre.
Register: <https://sydneyalgorithms.wordpress.com/2016/10/25/sydney-algorithms-workshop-2016/>
Focus is on parameterized complexity and computational geometry.
Nearby events happen the following week: ISAAC 2016 (Sydney), the Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (ACCMCC 2016 in Newcastle), and the workshop on Applied Probability, Combinatorics and Optimisation
(APCO in Newcastle).
Workshop: Combinatorial Optimization meets Parameterized Complexity
Where: Bonn at Universitätsclub Bonn, located at Konviktstraße 9, 53113 Bonn.
When: 13th and 14th of December 2016.
Organizers: Britta Peis, Heiko Röglin, and Stefan Kratsch.
Register: FREE, but send an email with the subject “Workshop Registration” to
ed.nnob-inu.sc|5terces#ed.nnob-inu.sc|5terces containing your name, address, and affiliation. Please indicate whether you will be attending both or just one day of the workshop.
Further information can be found at http://tcs.cs.uni-bonn.de/doku.php?id=research:workshop2016
PACE REPORT-Congratulations to all participants, committees, encouragers and the entire community.
TRACK A: Treewidth had submissions from ten universities: Brown, Frankfurt, IIT Madras, UC Irvine, Karlsruhe, Lübeck, Meiji, Sydney, TU Wien, and Utrecht.
TRACK A WINNERS
Computing treewidth optimally with a sequential algorithm:
1st prize, 350e Hisao Tamaki (Meiji University)
2nd prize, 125e Hans Bodlaender, Tom van der Zanden (Utrecht University)
3rd prize, 75e Max Bannach, Sebastian Berndt, Thorsten Ehlers (Luebeck University)
Computing treewidth heuristically with a sequential algorithm:
1st prize, 350e Ben Strasser (Karlsruhe Institute of Technology)
2nd prize, 125e Eli Fox-Epstein (Brown University)
3rd prize, 75e Michael Abseher, Nysret Musliu, Stefan Woltran (TU Wien)
Computing treewidth heuristically with a parallel algorithm:
1st prize, 350e Kalev Kask, William Lam (University of California at Irvine)
2nd prize, 125e Ben Strasser (Karlsruhe Institute of Technology)
3rd prize, 75e Max Bannach, Sebastian Berndt, Thorsten Ehlers (Luebeck University)
TRACK B: Feedback Vertex Set had submissions from six universities: Bonn, Chennai, Kiel, Moscow (two teams), National Institute for Informatics NII Japan, Saarbrücken, and Tokyo.
TRACK B WINNERS
Computing optimal feedback vertex sets:
1st prize, 500e Yoichi Iwata (National Institute of Informatics (NII)) and Kensuke Imanishi (University of Tokyo)
2nd prize, 300e Marcin Pilipczuk (University of Warsaw)
3rd prize, 200e Ruben Becker, Karl Bringmann, Dennis Gross, Erik Jan van Leeuwen, Natalie Wirth (MPI Saarbrücken)
See the full Report in the IPEC proceedings and at the website (https://pacechallenge.wordpress.com.)
Congratulations to Magnus Wahlström who has just got past probation at RHUL — a nice milestone! He also has received an EPSRC First Grant scheme grant, which It pays for one postdoc for one year, plus conference travels. Topic: "Polytope methods in parameterized complexity".
https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0916-292
The ad runs for a relatively short time (deadline October 4th). Candidates for whom this is causing problems should contact Magnus directly.
Congratulations for best paper awards Last week there were 2 simultaneous general algorithms conferences whose best paper award went to a paper from the FPT community. Stefan Kratsch won the best paper award at ESA 2016 for his paper ''A randomized polynomial kernelization for Vertex Cover with a smaller parameter''. Bart Jansen and Astrid Pieterse won the best paper award at MFCS 2016 for their paper ''Optimal Sparsification for Some Binary CSPs Using Low-degree Polynomials''. Congratulations to all!
Congratulations to R. B. Sandeep on his excellent research, and many thanks to him for adding another "Table of Races" on the Complexity Status of Edge Modification Problems (See the page in the Menu on the right column of this Welcome page).
Be sure to "Friends" our new FPT facebook page started by Fran Rosamond. It is called: Mike Fellows - FPT Multivariate Algorithmics
Congratulations to ICALP Dissertation winners. Here they are being introduced by Luca Aceto. Georg Zetzsche:
"Monoids as storage mechanisms", Radu Curticapean: "The Simple, Little and Slow Things Count: On Parameterized Counting Complexity", and Heng Guo: "Complexity Classification of Exact and Approximate Counting Problems."
Update to PACE the 1st Parameterized Algorithms and Computational Experiments Challenge – Look for the PACE Session at IPEC 2016!
Thanks to the generous support of the NWO Gravitation project NETWORKS (http://thenetworkcenter.nl/), we canannounce the following Travel Awards and prizes for the first PACE challenge.
Three Travel Awards of 500 € each are available to help young researchers attend IPEC 2016. Apply by e-mailing a CV and a motivation letter by 20 July to on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF (Univ Bergen) Chair of the Steering Committee. To be eligible one must
– submit a working implementation in one of the PACE challenges,
– be a full-time student (undergraduate or graduate level, excluding PhD students),
— commit to attending IPEC 2016 in case one receives the travel award.
Competition prizes. Track A offers four ranked challenges: Exact sequential, Exact parallel, Heuristic sequential, and Heuristic parallel computation of Treewidth. For each ranked challenge, there will be a first, second, and third prize. Track B offers one ranked challenge and there will be altogether three prizes for Feedback Vertex Set.
See details on the PACE website https://pacechallenge.wordpress.com.
Update to Creative Mathematical Sciences Communication (CMSC) – Luebeck, Germany 4—7 October 2016 (http://www.tcs.uni-luebeck.de/cmsc)
Join Tim Bell and Mike Fellows (authors of Computer Science Unplugged!), Joek van Montfort (Scratchweb Foundation and CoderDojo), and other fun, creative folks interested in exploring new ways of popularizing computational thinking, algorithmic thinking, and the foundations and frontiers of computing. We encourage you to present your own efforts and demonstrate / discuss new ideas with outdoor activities, storytelling, art, dance, coding, lecture or other activities. This is Computer Science Unplugged! (www.csunplugged.org) and beyond! Ideas for round-table discussions welcome.
Send an Abstract of what you would like to do to Rudiger Reischuk (ed.kcebeul-inu.sct|kuhcsier#ed.kcebeul-inu.sct|kuhcsier) or Sebastian Berndt (ed.kcebeul-inu.sct|tdnreb#ed.kcebeul-inu.sct|tdnreb). Send a rough outline of your activity as soon as possible, please. This will help us prepare a program. Provide a title, a few descriptive sentences and let us know how much time you need. We accept later submissions due to the concept of this conference.
Michael Fellows made Order of Australia, Companion to the Queen. For eminent service to higher education, particularly in the field of theoretical computer science, as a leading academic, researcher and author, as a mentor, and through public outreach programs particularly for children. Mike and Fran are deeply honoured and humbled by this honour, and extend our congratulations and appreciation to the entire parameterized complexity and Computer Science Unplugged communities.
Congratulations! Jason Crampton, Gregory Gutin and Remi Watrigant won the best paper award at SACMAT 2016. For Jason Crampton and Gregory Gutin it's the second in a row: they won one at SACMAT 2015 as well. Both SACMAT 2015 and 2016 papers deal with FPT algorithms for access control problems. SACMAT is an IPEC analog for the infomation access control community.
Publication of FPT papers. Data collected by Bart Jansen.
See article in the Parameterized Complexity Newsletter, May 2016.
3rd CREATIVE MATHEMATICAL SCIENCES COMMUNICATION CONFERENCE (CMSC)
4 - 7 October 2016, Luebeck, Germany
http://www.tcs.uni-luebeck.de/cmsc
Explore new ways of popularizing computational thinking underlying computer science with outdoor activities, storytelling, art, dance, and various coding activities. This is Computer Science Unplugged! (www.csunplugged.org) and Beyond!
Join others interested in computational thinking, algorithmic thinking, and the frontiers and foundations of computing. We encourage you to present your own efforts and discuss new ideas. Demonstrations welcome, as also ideas for leading round-table discussions.
Important dates:
Abstracts: As soon as possible, please send a rough outline of your activity. This will help us to prepare a program. Provide a title, a few descriptive sentences and let us know how much time you need. We have said 10 June, but we accept later submissions due to the concept of this conference. Final submissions will be handled later on separately. The final submission should contain 5 to 12 pages.
Submissions due: 8 July 2016
Early Registration: 15 August 2016
Conference: 4-7 October 2016
Contacts:
Rudiger Reischuk ed.kcebeul-inu.sct|kuhcsier#ed.kcebeul-inu.sct|kuhcsier
Sebastian Berndt ed.kcebeul-inu.sct|tdnreb#ed.kcebeul-inu.sct|tdnreb
Frances Rosamond on.biu|dnomasor.secnarf#on.biu|dnomasor.secnarf
Tribute to DAVID JOHNSON, creator of DIMACS Challenge and a leader in Theoretical Computer Science and algorithms.
The 1st Parameterized Algorithms and Computational Experiments Challenge (PACE) is respectfully dedicated to the memory of Professor David Johnson, a Computer Science leader and visionary.
Details are on the website https://pacechallenge.wordpress.com
Register your team NOW.
Benchmark instances available NOW.
Track A: Tree Decomposition: optimal solutions, heuristics, generating hard instances,
and collecting real-world instances. The tree decomposition validator is now available: https://github.com/holgerdell/td-validate/
GitHub holgerdell/td-validate td-validate - A validity checker for tree decompositions
Track B: Feedback Vertex Set: fixed-parameter algorithms.
IMPORTANT DATES
• 1 June 2016: Register participation. Track A for TreeWidth send email to Holger Dell at moc.lledregloh|61ecap# moc.lledregloh|61ecap and for Track B Feedback Vertex Set send email to ed.anej-inu|zciweisumoK.naitsirhC#ed.anej-inu|zciweisumoK.naitsirhC
• 1 August 2016: DEADLINE TO SUBMIT Implementations.
• 22–26 August 2016: Results announced at the International Symposium on Parameterized and Exact Computation (IPEC 2016).
GOALS: PACE investigates the applicability of algorithmic ideas studied and developed in the subfields of multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms. It aims to:
• Bridge between algorithms design and analysis theory and algorithm engineering practice
• Inspire new theoretical developments
• Produce universally accessible libraries of implementations and repositories of benchmark instances
• Encourage the dissemination of these findings in scientific papers
The focus for the inaugural PACE 2016 is to identify specific challenge problems and explore possible organisational models to implement the main goals. It is expected that lessons learned from PACE 2016 will be incorporated into future studies. Researchers are encouraged to join or contact the Steering Committee to influence these developments.
2016 PACE Programme Committee
• TRACK A: Holger Dell (Saarland University, Simons Institute for the Theory of Computing ) and Thore Husfeldt (Lund Univ, IT Univ of Copenhagen)
• TRACK B: Falk Hüffner (TU-Berlin) and Christian Komusiewicz (Friedrich-Schiller-Universität Jena)
PACE Steering Committee
• Holger Dell (Saarland University, Simons Inst for the Theory of Computing )
• Thore Husfeldt (Lund Univ, IT Univ of Copenhagen)
• Bart M. P. Jansen (Eindhoven Univ of Technology)
• Petteri Kaski (Aalto University)
• Christian Komusiewicz (Friedrich-Schiller-Universität Jena)
• Amer Abdo Mouawad (Univ Bergen)
• Frances Rosamond (Chair)(Univ Bergen) EMAIL: on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF
PRIZES: We expect to award prizes but these are not yet finalized.
Please alert your programming students.
3rd CREATIVE MATHEMATICAL SCIENCES COMMUNICATION CONFERENCE (CMSC)
The Creative Mathematical Sciences Communication conference (CMSC) explores new ways of popularizing the rich mathematics underlying computer science including outdoor activities, art, dance, drama and all forms of storytelling. How do you explain your research to your colleagues down the hall, in different disciplines, government, your kids, mom.
Date: 4-7 October 2016
Location: Lübeck, Germany
Abstracts due: 10 June 2016
Submissions due: 8 July 2016
Early Registration: 15 August 2016
Website http://www.tcs.uni-luebeck.de/cmsc/
This is the third event in a conference series that explores new ways of helping students to achieve 21st Century competencies in mathematics and computer science. The previous conferences, held in Darwin, Australia, in 2013 and in Chennai, India, in 2014 (Videos from 2014) saw a unique interaction between computer science / mathematics researchers and educators and artists (theatre, dance, graphic arts).
The CMSC has several aspects.
• Involve and support researchers to share the frontiers of computer science and mathematics with children and the general public.
• Research communication is a “two-way street”. Explaining your research can inspire new research questions. For example, Mike Fellows describes how “Kid Crypto” inspired the new research of Polly Cracker crypto systems.
• Future directions of Computer Science Unplugged! Discuss with Tim Bell, Mike Fellows and others future directions of this grass-roots movement, which is now translated into 19 languages.
• Storyfull, whole-body, kinesthetic math activities. Demonstrate and design new whole body activities that connect math with the inner self and community. Design activities that include cultural understanding and relevance. Demonstrate activities that foster curiosity, enthusiasm and perseverance.
• Expand computational thinking across the curriculum, and explore how mathematical thinking strategies nurture 21st Century competencies.
• Policy makers in government, business and industry. What are the issues and unanswered questions of executives and policy makers?
The Parameterized Complexity Newsletter for Dec 2015 is on the newsletter page here. The Newsletter reports on an excellent workshop organized by Thore Husfeldt and D´aniel Marx at the Simons Institute as part of the semester on Fine-Grained Complexity, where one of the topics was FPT inside of P, discussed by George Mertzios in this newsletter. In a different direction, a conversation has started about holding an FPT Implementation Challenge. The importance of implementation and appreciation for this work is discussed in the article by Gregory Gutin. Read the New Ideas Section by Mike Fellows about Realistic Modeling. Enjoy the Newsletter and Happy Holidays. Mike and I have new email addresses starting January: on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF and on.biu.ii|swolleF.leahciM#on.biu.ii|swolleF.leahciM
FPT IMPLEMENTATION CHALLENGE
Join the discussion taking place right now about an FPT Challenge. What problem, data-sets should we use? When will it take place? Join the discussion on SLACK. Send an email now to Holger Dell (ed.dnalraas-inu.icmm|lledh#ed.dnalraas-inu.icmm|lledh) or Fran Rosamond ( on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF)
EATCS-IPEC NERODE PRIZE 2016
Nominations: due February 15, 2016 for outstanding papers in the area of multivariate algorithmics meant in a broad sense, and encompasses, but is not restricted to, those areas covered by IPEC.
Eligibility: 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 year of publication should be at least two years and at most ten years before the year of the award nomination. 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.
Nominations: 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"
The award is presented annually with the presentation taking place at IPEC (International Symposium on Parameterized and Exact Computation). IPEC 2016 takes place within ALGO 2016, August 22-26, 2016, Aarhus, Denmark.
Award Committee
David Eppstein (University of California, Irvine)
Daniel Marx (Hungarian Academy of Sciences)
Jan Arne Telle (University of Bergen, Norway. Chair)
For further information, including former winners, see: [http://www.eatcs.org/index.php/nerode-prize]
CONGRATULATIONS TO MAREK CYGAN for a 2015 ERC Starting Grant for the project: Technology transfer between modern algorithmic paradigms, funded by approximately 1.48M Euro over 5 years. The project focuses on (a) parameterized complexity, (b) approximation algorithms, and (c) metaheuristics.
CONGRATULATIONS TO MEIRAV ZEHAVI for several awards,including the 2016 Women Postdoctoral Fellowship of Israel's Council for Higher Education (awarded to excellent female students). Mirav was also awarded the Best Student Paper Award at IWOCA'15, Best Student Paper Award at ESA'15, and Best Student Paper Award at MFCS'15. She has a Simons-Berkeley and I-CORE Joint Research Fellowship 08/2015 - 05/2016.
CONGRATULATIONS TO CHRISTINA BOUCHER, CHRISTINE LO and DANIEL LOKSHTANOV for winning the ESA 2015 Best Paper Award with Consensus Patterns (Probably) has no EPTAS.
CONGRATULATIONS TO MANUEL SORGE and STEFAN KRATSCH for the IPEC'15 Excellent Student Paper Award with On Kernelization and Approximation for the Vector Connectivity Problem.
CONGRATULATIONS TO RENE VAN BEVERN, CHRISTIAN KOMUSIEWICZ and MANUEL SORGE for the ATMOS'15 Best Paper Award with Approximation algorithms for mixed, windy, and capacitated arc routing problems.
CONGRATULATIONS TO RADU CURTICAPEAN for receiving the 2015 Best Student ICALP Paper Award, Track A, with Block Interpolation: A framework for tight exponential-time counting complexity. In 2013, Radu was awarded the Best Student ICALP Paper Award, Track A, with Counting matchings of size k is #W[1]-hard. ICALP best student paper awards are given to papers that are solely authored by students. Radu will finish his PhD. with Markus Blaser this summer, and has accepted a post-doc position with Daniel Marx.
CONGRATULATIONS TO JASON CRAMPTON, GREGORY GUTIN, DANIEL KARAPETYAN, Royal Holloway, University of London, for receiving the Best Paper Award at ACM SACMAT 2015 with Valued Workflow Satisfiability. The paper studies
theoretically and experimentally an FPT algorithm for a new generalization of a well-known problem in access
control.
CONGRATULATIONS TO SAKET SAURABH and DANIEL LOKSHTANOV with FOUR papers at ICALP. This is the second time for Saket!
CONGRATULATIONS TO ALL with conference papers accepted. See Bart’s list on this wiki.
IPEC 2015: 10th International Symposium on Parameterized and Exact Computation covers research in all aspects of parameterized and exact exponential-time algorithms and complexity. In particular, studies on parameterized and exact computations for real-world applications and algorithmic engineering are especially encouraged.
Excellent Student-Paper Award
A paper is eligible for the award if at most one of its authors has received a PhD degree before the paper submission deadline. If there is a non-student author, the students' contributions must be substantial, and a student must give the presentation at the conference.
Accepted Papers
Accepted papers will be published in the symposium proceedings. Authors of accepted papers must present their work at the symposium.
Journal Special Issue
Authors of selected papers at IPEC 2015 will be invited to submit extended versions to a special issue of Algorithmica.
Important dates
• Abstract submission deadline: 26 June 2015, 23:59 UTC/GMT
• Paper submission deadline: 28 June 2015, 23:59 UTC/GMT
• Notification date: 25 July 2015
• Symposium: 16-18 September 2015
• Final version due: 30 September 2015, 23:59 UTC/GMT
IPEC is part of ALGO 2015. Dates for IPEC are 16—18 Sept. in Patras, Greece. ALGO is held 14—18 Sept. A special event will be organized during ALGO 2015 for honoring Paul Spirakis on the occasion of his 60th birthday.
SOCIAL CHOICE: 7th Summer Workshop of the Centre for Mathematics in Social Science of the Univ. of Auckland, NZ.
DATES: 18-19 February 2016.
TOPIC: Multi-Winner Elections—includes Complexity Theory to Social Choice to Political Science.
INVITED SPEAKERS: Bernard Grofman (UC, Irvine), Charles Plott (Caltech), Jean-Francois Laslier (Paris School of Economica), Rolf Niedermeier (Technical Univ. Berlin), Piotr Faliszewski (AGH Univ. Technology, Krakow).
CONTACT: Prof. Arkadii Slinko (zn.ca.dnalkcua|oknils.a#zn.ca.dnalkcua|oknils.a)
Michael Fellows named Honorary Fellow of the Royal Society of New Zealand
Remember those scientists that inspired awe in us as children? Einstein, Marie Curie, Charles Darwin, Sir Arthur Eddington, Sir Alexander Fleming, and many more are also Honorary Fellows RSNZ. Congratulations, Michael.
Congratulations to Bingkai Lin. SODA PC has decided to give both the Best Paper Award and the Best Student Paper Award to the biclique paper by Bingkai Lin. http://www.siam.org/meetings/da15/paper.php
k-BI-CLIQUE is W[1]-hard!
The k-BI-CLIQUE problem asks, given a graph G and integer k, whether G contains the complete bipartite graph $K_{k, k}$ as a subgraph. While this problem was long conjectured to be W[1]-hard, for a long time no one was able to give a proof. This earned the k-Biclique problem the first place in the open problem list of the new version the textbook by Downey and Fellows, listed among "The Most Infamous". But a W[1]-hardness proof has been found! Bingkai Lin, a PhD student in Tokyo, gave a parameterized reduction from k-Clique to prove that k-Biclique is W[1]-hard. His paper can be found on the arXiv. The crux of the proof is to find bipartite host graphs satisfying certain conditions, that allow a k-Clique instance to be embedded in them. Binkai gives a deterministic construction of such host graphs using Weil's character sum theorem, which transforms a k-Clique instance into a Biclique instance whose parameter value is roughly (k!). There is also a randomized construction that is more efficient, resulting in a parameter value of $k^2$. It implies that under a randomized version of the Exponential Time Hypothesis, k-Biclique cannot be solved in $f(k) n^{o(\sqrt{k})}$ time. We congratulate Binkai with this great result!
HAPPY BIRTHDAY JIANER CHEN!
Friends gathered for 60th birthday celebrations for Jianer in College Station, Texas and at South-Center Univ in China. The Tsinghua Science and Technology Journal Vol. 19 No. 4/August 2014 is a Special Issue on Parameterized Complexity in honour of Chen's birthday. Guest edited by Liming Cai, Iyad Kanj, and Frances Rosamond.There are eight articles of recent results and surveys. Congratulations, Jianer!
The 2014 September Parameterized Complexity Newsletter is on the newsletter page. Inside are many announcements of grants, awards,and graduations, new research,and conferences. Enjoy!
Christiaan Huygens Prize goes to Bart Jansen
Congratulations to Bart Jansen, Univ. Bergen, for winning the Christiaan Huygens award. This prestigious prize is awarded once every 5 years in the area of ICT for a PhD thesis that contributed significantly to science and has clear relevance to society. The prize consists of 10 000 Euros and a bronze statue of the Dutch scientist Christiaan Huygens. The head of the Dutch scientific funding agency NWO, and the Minister of Education, Culture, and Science presented the award. The award is partly sponsored by IBM, and an interview with Bart is on the IBM weblog:
IBM
http://asmarterplanet.com/blog/2014/06/qa-bart-jansen-winner-prestigious-huygens-prize.html
Bart says: I was really honored, and very happy to meet all these people and share my passion for science with them. During the evening there was an interview with the 4 nominees. They asked us what really helped us in our research; my answer was that the opportunity to travel and meet other people in the field has really helped me grow. During my acceptance speech I told the entire audience about my trip to Australia, surfing and and doing research with Mike and Fran, and about the great and friendly community that I am lucky to be part of. (Photo credit goes to Martine Siemens.)
The 2014 June Parameterized Complexity Newsletter is on the newsletter page. Inside are many announcements of grants, awards,and graduations, new research,and conferences. Enjoy!
Humboldt Research Award to Toby Walsh
Congratulations to Toby Walsh, UNSW, NICTA,for a prestigious Humboldt Research Award.
Inaugural 2014 EATCS Fellow Fellows
Congratulations to Michael Fellows, Australian Professorial Fellow, Charles Darwin University.
Meltzer Prize to Michal Pilipczuk
Congratulations to Michal Pilipczuk, U. Bergen, for
the 2014 Meltzer Prize for Young Researchers.
DFG Award to Mattias Mnich
Congratulations to Mattias Mnich, Bonn, for a DFG award for the project, Big Data Ker-
nelization.
DFG Mercator to Piotr Faliszewski
Congratulations to Piotr Faliszewski, AGH U. Krakow for a DFG Mercator Guest Professorship.
PCCR 2014: 2nd Workshop on the Parameterized Complexity of Computational Reasoning
July 17-18, 2014 in Vienna, Austria.
PCCR 2014 will be part of the Vienna Summer of Logic, the largest logic event in history with an expected 2,500 participants.
Invited speakers include Georg Gottlob, Dániel Marx, and Stefan Szeider.
Abstracts of contributed talks are due on May 9, 2014 May 12, 2014.
Please see the Workshop webpage for the submission of abstracts and registration information.
Special Issue in journal "Algorithms"
There will be a special issue on "Parameterized Algorithms - Challenges from Real-World Applications" in the open-access journal Algorithms published by MDPI. The submission deadline is 31 May 2014, but you may send your manuscript at any time before then. If you plan to contribute a research or review article, please send a short abstract to the Editorial Office (moc.ipdm|smhtirogla#moc.ipdm|smhtirogla).
Submissions should study the parameterized complexity of NP-hard problems arising from application areas including (but not limited to) network analysis (biological, social, and technical), computational geometry, SAT solving, bioinformatics, string problems, operations research and combinatorial optimization, computational
social choice, data clustering, and mining.
Particularly welcome are submissions that introduce practically relevant problem formulations and/or parameterizations, present linear-time fixed-parameter tractability and/or kernelization results, or that take into account aspects of algorithm engineering.
This special issue is edited by Christian Komusiewicz, Stefan Kratsch, and Rolf Niedermeier. The guest editors and the editorial office aim for a rapid publication process. The journal levies an Article Processing Charge for accepted papers,
currently 300 CHF (Swiss Francs) per accepted paper.
More info including a detailed call for submissions can be found at http://www.mdpi.com/si/algorithms/Parameterized_Algorithmics
SCHOOL ON PARAMETERIZED ALGORITHMS AND COMPLEXITY
DATES: Monday, 18th August — Friday, 22nd August 2014 at the Conference Center in Będlewo, Poland.
CONTENTS: Basic introductory courses as well as an overview of very recent developments, including many exercises and open problems. We target interested master students, grad students and young researchers willing to join the research in parameterized algorithms and complexity. However, even more experienced participants will find many of the presentations interesting and fruitful.
FEE around 250 euros (to be determined later) will cover accommodation and full board. We expect to be able to provide support for interested researchers with funding difficulties.
The workshop is supported by European Research Council grants "Rigorous Theory of Preprocessing" (no. 267959) and "Parameterized Approximation" (no. 306992), and by Warsaw Center of Mathematics and Computer Science.
MORE INFO: http://fptschool.mimuw.edu.pl
CONTACT: lp.ude.wumim|loohcstpf#lp.ude.wumim|loohcstpf
Erasmus Mundus grants
The Erasmus Mundus offers grants for scientists at any level to visit their consortium universities. Grant deadline is 15 February 2014. See https://sites.google.com/site/emthelxinoe/call.
Associated universities are: Malaga, Montpellier, Athens, Wroclaw, Kosice, Dresden, University of Newcastle Australia, Wollongong UOW Wollongong, La Trobe, Melbourne, Victoria Univ Wellington. Email: ua.ude.eltsacwen|otacsoM.olbaP#ua.ude.eltsacwen|otacsoM.olbaP
Please post JOB opportunities the JOBS page. For example:
Applications close: Wednesday 05 March 2014. Research Associate, University of Newcastle, Australia. Develop a research program using supercomputer-based approaches together with memetic algorithms, to address key areas in graph optimization. See: http://www.seek.com.au/job/25987255. For more information, email: ua.ude.eltsacwen|otacsoM.olbaP#ua.ude.eltsacwen|otacsoM.olbaP
New course in PC
See http://www.stanford.edu/~rrwill/cs266.html for the description of CS266 — Parameterized Algorithms and Complexity, the Stanford course taught by Ryan Williams last spring.
ETH Zurich ABZ International Medal of Honor to Michael Fellows
Congratulations to Michael Fellows, Australian Professorial Fellow, Charles Darwin University. Mike has been presented with the ETH Zurich ABZ International Medal of Honor for fundamental contributions to Computer Science Education, one of the highest possible honours in Computer Science Education circles worldwide, at an award ceremony at the annual Swiss Computer Science Day in Zurich, Switzerland on January 7. The medal was awarded for the worldwide impact of the innovative book Computer Science Unplugged!, written by Professor Fellows with New Zealand colleagues Tim Bell (Uni of Canterbury, NZ) and Ian Witten (Otago Univ, NZ). The concept is aimed at presenting the mathematical ideas of computer science to primary school students. It has been translated into 18 languages and has spurred a global grass-roots movement (see www.csunplugged.org).
“The plan was to develop materials based around modern research in computer science and mathematics and have these ideas used to make early education more exciting and engaging,” Professor Fellow said. “Woven through “Computer Science Unplugged” is the importance of story: that presenting math and computing topics through story-telling and drama can captivate children and adults alike, and provides a whole new level of engagement with what can be perceived as a dry topic. It is also about not paying attention to boundaries, whether teaching advanced computer science concepts to elementary school children or running a mathematics event in a park."
Frances Rosamond was invited to the stage with Mike, and Juraj Hromkovic presented them with the beautiful oil painting.
Fabrizio Grandoni wins ERC Starting Grant
Congratulations to Fabrizio Grandoni, Algorithms and Complexity Group of IDSIA, University of Lugano (Switzerland) for the ERC Starting Grant New Approaches to Network Design. The grant is supporting a PostDoc position in algorithms. Contact moc.liamg|inodnarG.oizirbaF#moc.liamg|inodnarG.oizirbaF
Danny Hermelin receives EU Award
Congratulations to Danny Hermelin, Ben-Gurion University of the Negev, who has received 100K Euros for a period of 4 years for his proposal: "MetaKer - New Directions in Meta-Kernelization." The grant's name is "Marie Curie Career Integration Grant" and it is given by the EU as part of the Marie Curie Auctions. Well done, Danny.
DFG Award to Gabor Erdelyi
Congratulations to Gabor Erdelyi, Univ Seigen, who has received a 167.000,00 Euros, two-year award for the project that includes parameterized and average-case complexity of decision-making problems. All the best to Olivia, Gabor and little Alex.
The Parameterized Complexity Newsletter, Vol 9, no 3, November 2013 is on the wiki. Congratulations to award winners Gregory Gutin, Stefan Szeider, Tobias Freidrich, Frank Neumann, and IPEC Excellent Student Paper Award Winners: Mateus de Oliveira Oliveira, Bart Jansen, Lukas Mach, and Tomas Toufar. There are two excellent articles, and announcements about the Nerode Award.
DAAD Grant to Katrin Casel
Congratulations to Katrin Casel, who has received a DAAD grant to visit Dr. Ljiljana Brankovic, Univ. Newcastle, Australia. Katrin is a PhD student of Prof. Dr. Henning Fernau.
Australian Research Council Award to Tobias Freidrich and Frank Neumann
Congratulations to Tobias Freidrich, Friedrich Schiller Univ–Jena and Frank Neumann, Univ Adelaide for a 300k Australian Research Council Award for Parameterised Analysis of Bioinspired Computing, 2014–2016.
Royal Society Wolfson Research Merit Award to Gregory Gutin
Congratulations to Prof. Gregory Gutin at Royal Holloway, London for his project to study Parameterised Combinatorial Optimisation Problems. Gregory has been awarded the Royal Society Wolfson Research
Merit Award which provides a salary supplement for 5 years.
Austrian Science Fund Award to Stefan Szeider
Congratulations to Prof. Stefan Szeider at TU-Wein for a project to study Parameterized Knowledge Compilation. The project has been awarded a three-year Eur 340k Austrian Science Fund Award.
CALL FOR NOMINATIONS NERODE PRIZE 2014
The call for nominations for the 2014 EATCS-IPEC Nerode Prize is out. The deadline is January 1, 2014. More information can be found here.
IPEC 2013 Excellent Student Paper Awardees
Congratulations to Mateus de Oliveira Oliveira (KTH, Stockholm) for {\it Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs}, Bart M.P. Jansen (U. Utrecht) for {\it On Sparsification for Computing Treewidth}, and Lukas Mach (DIMAP, U. Warwick) and Tomas Toufar (Charles U., Prague) for {\it Amalgam Width of Matroids}. Mach accepted the award at the meeting.
The IPEC-2013 Report shows a record breaking 29 papers accepted out of 58 submissions. Thank you to the 2013 IPEC Committee Co-Chairs Gregory Gutin (Royal Holloway, U. London) and Stefan Szeider (Vienna U. of Technology).
The 2013 April Parameterized Complexity Newsletter is on the newsletter page. Inside are many announcements of grants, awards,and graduations, new research,and conferences.
NERODE PRIZE ANNOUNCED
The 2013 EATCS-IPEC Nerode Prize winners for outstanding papers in the area of multivariate algorithmics have been announced by the Nerode Prize 2013 Committee: Georg Gottlob (Oxford), Rolf Niedermeier (TU Berlin, chair), and Peter Widmayer (ETH Zurich).The committee has unanimously awarded Chris Calabro (Google Inc.), Russell Impagliazzo (UC San Diego), Valentine Kabanets (Simon Fraser U.), Ramamohan Paturi (UC San Diego), and Francis Zane (Alcatel Lucent). See eatcs.org for more information. Congratulations.
Vienna DBAI Group is 3-Time Winner
Congratulations to Prof. Dr. Reinhard Pichler and the Data-Base and Artificial Intelligence Group at TU-Wein for being awarded three
FWF Austrian Science Fund awards.
The FAIR project, {\it Fixed-Parameter Tractability in Artificial Intelligence and Reasoning} studies the parameterized complexity of logic based problems such as answer-set programming and description logics. Awarded 350k EUR.
The D-FLAT project, {\it Extending the Answer-Set Programming Paradigm to Decomposed Problem Solving} combines tree decomposition techniques with the declarative language “answer-set programming” (ASP). It extends Group previous work, including a tool that allows to specify a dynamic programming algorithm by means of ASP and serves for rapid prototyping of algorithms that exploit bounded treewidth. Awarded 280k EUR.
The project FAIR: {\it Fragment-Driven Belief Change} studies belief revision, update, and merging, which are subareas of Artificial Intelligence that deal with incorporating new information into existing knowledge bases. A part of the project is devoted to a parameterized complexity analysis of these problems. Awarded 350k EUR.
AMS Special Session on Mathematical Underpinnings of Multivariate Complexity Theory and Algorithm Design, and Its Frontiers and the Field of Incrementalization
took place at the Joint Mathematics Meetings in San Diego. There were two days of excellent presentations. Anil Nerode, Mike Fellows, Annie Liu and Rod Downey gave a final summary. Here are (SLIDES), and (ABSTRACTS).
First International Conf on Creative Mathematical Sciences Communication. 2013 Theme of Computer Maths and Curiosity, Art, Story. August 2—10, 2013, Darwin. Preceded by 'Not-About-Graphs III' on July 31/August 1. Extensive website: www.cdu.edu.au/conference/csmaths
Mike Fellows has long wanted mathematical sciences outreach to be a respected research area. Take Computer Science Unplugged! to the next level. Mike Fellows and Tim Bell will help us create new cs maths activities incorporating Indigenous, Both-Ways, 21C Competencies, computational thinking to be used in ALL subjects, across curriculum.
The conference will include an excursion into the Outback of the Northern Territories. Contact ua.ude.udc|dnomasoR.secnarF#ua.ude.udc|dnomasoR.secnarF.
Please announce the conference on mailing lists and websites where it may be of interest.
Congratulations to Ivan Bliznets and Alexander Golovnev, both of St. Petersburg University of the Russian Academy of Sciences. The 2012 IPEC Program Committee has selected their paper, A New Algorithm for Parameterized MAX-SAT, for the IPEC 2012 Excellent Student Paper Award. Ivan Bliznets accepted the award at the meeting.
Erik Demaine and Mohammad Taghi Hajiaghayi, in the past three months, have been awarded two very competitive grants. The first from DARPA with 1 million each and the second NSF midsize (400K Erik and 200K Mohammad) on fixed parameter algorithms for graph problems and its connection to other fields. So in total, just in the past three months, they have been awarded 2.6 million USD. We can say now in the past three months the whole community has gotten about 8 million Euro in the field, which is very impressive.
The August 2012 Parameterized Complexity Newsletter is on the wiki. Over 5 million Euros in new research funding has been awarded to research groups in the PC community. See some of the winners in the picture. Please join the mailing list if you would like an email notification: mailing list enrolment Instructions. Everybody who subscribes receives an email where (s)he needs to confirm the subscription, without needing approval. If you have changed email address, please un-subscribe and then resubscribe with your new address.
The 2012 WorKer (Kernelization) held at Dagstuhl (filled to overflowing) was brilliant, inspiring, warm, loving——fabulous! Many thanks to organizers and everyone who came and to those who wanted to come but couldn't. Thursday talks celebrated Mike Fellows' birthday, describing the early history of the field and many future directions. Fran Rosamond described Mike's outreach of Computer Science Unplugged! and Mathematical Passion Plays. Rod Downey presented a mysterious pile under a white cloth. The Festschrift, “The Multivariate Algorithmic Revolution and Beyond” (Springer LNCS 7370) was revealed when Mike pulled aside the cloth. Authors are in the photo. Mike is 'walking on air' very happy!!
The May 2012 Parameterized Complexity Newsletter is on the wiki. There are excellent articles and announcements. Please join the mailing list if you would like an email notification: mailing list enrolment Instructions. Everybody who subscribes receives an email where (s)he needs to confirm the subscription, without needing approval. If you have changed email address, please un-subscribe and then resubscribe with your new address.
NEWS: The "AND-Conjecture solved!! Andrew Drucker, MIT, has new results. A preliminary version of his paper, "New Limits to Classical and Quantum Instance Compression", is available at http://people.csail.mit.edu/andyd/papers.html. See also AND-Conjecture at http://intractability.princeton.edu/blog/2012/03/theory-lunch-february-17. Bodlaender et al. (ICALP 2008) showed that the intractability of "OR-compression" would have important consequences in the study of FPT problems. They showed something similar for the corresponding "AND-compression," but it still remained mysterious. Andy has promised an article for our next newsletter. See the related article, “The AND-Conjecture may be Necessary” by Magnus Wahlstrom, MPI (Nov 2011 FPT Newsletter).
Congratulations to Yiannis Koutis, who has been awarded an NSF CAREER AWARD for his proposal about spectral graph theory and linear time algorithms. Together with another internal grant, he will be managing about 600K over the next 5 years. Yiannis is in the Computer Science Dept. at the Univ. Puerto Rico, Rio Piedras.
Congratulations to Rod Downey, who has been awarded the 2011 Hector Medal by the New Zealand Royal Society for outstanding work in mathematical and information sciences by a New Zealand researcher. Rod was awarded the medal for his influential and innovative work in mathematical logic. Ernest Rutherford was a recipient in 1916.
Congratulations to Serge Gaspers, who has been awarded the Australian DECRA for 375,000AUD for his project, “Solving intractable problems: from practice to theory and back”. Serge has accepted a PostDoc at UNSW with Toby Walsh.
Congratulations to Mohammad Taghi Hajiaghayi, who during 2011 has been awarded the prestigious Office of Naval Research (ONR) Young Investigator Award, an NSF CAREER Award, and a Google Faculty Research Award with total more than 1M dollars.
Congratulations to Yoichi Iwata for the 2011 IPEC Excellent Student Paper Award for “A Faster Algorithm for Dominating Set Analyzed by the Potential Method”.
The November 2011 Parameterized Complexity Newsletter is here. Congratulations to Serge Gaspers and Mohammad Taghi Hajiaghayi for multiple awards, to Yoichi Iwata for the IPEC Excellent Student Paper award, and to others on new positions. This newsletter includes useful citation statistics by Mike Fellows. Neeldhara Misra has agreed to be Column Editor of a regular column about blogs. Magnus Wahlstr\"{o}m, Stefan Kratsch and Danny Hermelin have each contributed outstanding articles on latest results. There is an excellent report on WorKer, including Open Problems. The Table of Races is quite large, and so I have placed it at the end of the newsletter. Please help keep it updated at our community wiki {\bf www.fpt.wikidot.com}. We also report new available positions, conferences, and call for papers. This is a huge, power-packed newsletter.
Slides of talks about kernelization: Links to WorKer 2011 talks and the IPEC 2011 tutorial are now available from the techniques and methodology page.
Announced by Dániel Marx: Postdoc positions available in Budapest, Hungary in parameterized complexity & algorithms. Read more.
Announced by Klaus Jansen: Klaus' DFG proposal "Approximation algorithms for scheduling on unrelated processors" has been accepted, and he has an opening for a postdoc for three years. Contact <ed.leik-inu.kitamrofni|jk#ed.leik-inu.kitamrofni|jk>
Announced by Stephan Kreutzer: The Logic and Semantics Group at the Inst for Software Engineering and TCS at the Technical Univ, Berlin, is offering a fully funded Ph.D. studentship in the area of logic or graph theory. Closing date for applications is 28 Aug 2011. See http://logic.las.tu-berlin.de.
Algorithms key to faster computing, see article in The Australian August 9, 2011 about Mike Fellows. SMARTER algorithms, rather than computer hardware, will deliver greater improvements in computer speed, a leading researcher says. Article here:
http://www.theaustralian.com.au/australian-it/algorithms-key-to-faster-computing-speeds/story-e6frgakx-1226111261272
CONGRATULATIONS to Dániel Marx
awarded a prestigious European Research Council Starting Grant. Dániel's 1.15M EUR, 5-year project will start January 2012 in Budapest, Hungary. The project is “PARAMTIGHT: Parameterized complexity and the search for tight complexity results”.
The July 2011 Parameterized Complexity Newsletter is here. The July 2011 newsletter congratulates Dániel Marx on a 1.15M EUR award, Cristina Bazgan on an IUF, and Iyad Kanj on a Spirit of Inquiry Award. Breakthrough results of Stefan Kratsch and Magnus Wahlström are described by Mike Fellows. “Solving MSO-Definable Problems” are described by Alexander Langer, Felix Reidl, Peter Rossmanith, and Somnath Sikdar. “Constraint Satisfaction Problems Parameterized Above or Below Tight Bounds” are described by Anders Yeo. There are announcements of conferences, openings, and congratulations to new PhD and new positions. See all the newsletters by clicking here.
IPEC 2011 in Saarbrucken in September
Full description is here.
IPEC 2011 will be part of ALGO 2011, which also hosts ESA, WABI, WAOA, ATMOS, and ALGOSENSORS. ALGO 2011 will take place September 5-9, 2011 in Saarbr¨ucken, Germany.
NEW NEW New postdocs and other positions advertised. See the JOBS section.
Workshop on Parameterized Complexity—“NOT-ABOUT-GRAPHS!” and Problem-Solving Workshop Frequent updates on this wiki.
Website is here http://www.cdu.edu.au/parameterized-nag.
Location: Charles Darwin University, Northern Territory, Australia this August. DATES: 5, 6, 7, 8 August 2011, plus 9-13 August for Problem-Solving “walkabout”.
Starts 6pm on Friday everning August 5, and ends at noon on Monday August 8. On Tuesday morning 9 August, we will continue with a “Barbados style” Problem-Solving Workshop, traveling into the bush and working on flip-charts, and returning to Darwin on Saturday 13 August. See the Workshop section of this wiki for frequent updates on Participants List and Description and Program. For more information or letter of invitation email ua.ude.UDC|dnomasoR.secnarF#ua.ude.UDC|dnomasoR.secnarF.
CONGRATULATIONS**
IPEC Student EXCELLENT PAPER Award!**
Two outstanding papers. Very fine work.
- Jesper Nederlof and Johan M. M. van Rooij,
‘Inclusion/Exclusion Branching for Partial Dominating Set Set Splitting’.
- M. Praveen,
‘Small Vertex Cover Makes Petri Net Coverability and Boundedness Easier’.
The April 2011 newsletter appreciates the winners of the IPEC student excellent papers awards.
The November 2010 newsletter describes many achievements and awards. Fedor Fomin: ERC Advanced Grant. Daniel Lokshtanov: Bergen Research Foundation award and also Simons Foundation Postdoc at UCSD. Pinar Heggernes: Norwegian Research Council award. Igor Razgon: President of Ireland Young Researcher Award. Daniel Marx: Humboldt Fellowship for Experienced Researchers. Matthias Mnich: Philips Prize of the Royal Mathematical Society, Netherlands and post doc at Berkeley. Research grants to: Vlad Estivil-Castro, Mike Fellows, Frances Rosamond. Petr Hliney. Klaus Jansen. Saket Saraubh. Todd Wareham.
Congratulations, Mike Fellows!
Mike Fellows has been awarded an Australian Professorial Fellowship, beginning 2010 for five years for Multivariate Algorithmics: Meeting the Challenge of Real World Computational Complexity. The award is for an "outstanding researcher with proven international reputation to undertake research that is of major importance in its field and of significant benefit to Australia." We are proud of you, Mike.
Congratulations, Chunmei Liu!
Chunmei Liu has won the 2009 NSF CAREER award for her project titled, "CAREER: A Complete System for Protein Identification with Computational Approaches". The project uses parameterized complexity and tree decomposition. Chunmei received her Ph.D. in Computer Science at University of Georgia in 2006. Her advisor was Liming Cai, RNA-Informatics Group. She is currently an assistant professor at Howard University, Washington DC. The NSF CAREER award is the most prestigious award to faculty in their early careers.
Number of electrons as the parameter! Wow!
The reduced density matrix method and some complexity issuesby Bastiaan Braams, Emory University at the Fields Institute Thematic Program on Mathematics in Quantum Information.
“I will review the classical formalism of electronic structure theory that is based on the two-body reduced density matrix and associated representability conditions. The N-representability problem is unsolved and results from computational complexity theory indicate that it won't be solved in any concise form. I hope on the one hand to make clear that it doesn't matter, and on the other hand to outline the challenge of obtaining what could be called anyway a solution to the N-representability problem. Finally I will discuss the computational complexity of the Hartree-Fock problem. As an algebraic problem with general 2-body terms in the hamiltonian (not limited to Coulomb interaction) it is NP-hard, while in the setting of parameterized complexity theory, with the number of electrons as the parameter, it is W[1]-hard.”
Administrative parameters! Very interesting paper!
Symbolic Reachability Analysis for Parameterized Administrative Role Based Access Control
B Scott, D. Stoller, Ping Yang, Mikhail Gofman,C. R. Ramakrishnan. Presented at SACMAT’09.
From the abstract: Role based access control (RBAC) is a widely used access control paradigm. In large organizations, the RBAC policy is managed by multiple administrators. It is often difficult to fully understand the effect of an ARBAC policy by simple inspection, because sequences of changes by different administrators may interact in unexpected ways. Allowing administrative roles and administrative permissions to have parameters significantly enhances the scalability and practical applicability of the administrative model.
Structural Study on Proteins in Maize Silk: Parameterized Complexity Approach!
Published by the American Society of Agricultural and Biological Engineers, St. Joseph, Michigan www.asabe.org Citation: Computers in Agriculture and Natural Resources, 4th World Congress Conference, Proceedings of the 24-26 July 2006 (Orlando, Florida USA) Publication Date 24 July 2006 701P0606.
Authors: X. Huang
Keywords: proteins, protein tertiary structure, computational approach
gives a brief summary of a parameterized computational approach for the study of tertiary structures of extension protein variants in maize silk. The structure predictions will be used in future studies to design mutants with desired structural properties to transform into maize and test cell wall properties with these altered proteins.