Anyone wishing to receive the newsletter by email can sign onto Frances Rosamond’s mailing list (under the heading “Subscribing to Fptnews”) here:
[http://mrfellows.net/mailman/listinfo/fptnews_mrfellows.net]
The current setting is that 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.
- 2011 November
The November newsletter: Congratulations to Serge Gaspers who was awarded the UNSW Vice-Chancellor Award, and also the Australian Research Council Discovery Early Career Researcher Award (DECRA), and 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, and to Yoichi Iwata for winning an IPEC 2011 Excellent Student Paper Award. Articles: Some Notes on the Performance of the Field by Michael Fellows; The AND-conjecture may be necessary by Magnus Wahlstr¨om; Hierarchies of Inefficient Kernelizabilty by Danny Hermelin, and Co-nondeterministic Compositions by Stefan Kratsch. New blog column The Theory Blogosphere by Neeldhara Misra, Column Editor. Report and Open Problems from WorKer 2011 by Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider. Table of Races, announcements, workshops, Tutorial at CATS, new positions.
- 2011 July
The July 2011 FPT Newsletter congratulates D\'aniel Marx on a 1.15M EUR award, Cristina Bazgan on an IUF, and Iyad Kanj on a {\it Spirit of Inquiry Award}. Breakthrough results of Stefan Kratsch and Magnus Wahlstr\"{o}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.
- 2011 April
The April 2011 FPT Newsletter celebrates the Chennai IPEC 2010 and presents the CFP for 2011 IPEC joint with ALGO. It introduces the new ACM SIGACT Chapter in Shanghai. Key article is "Parameterized Complexity for Answer Set Programming" by Michael Morak, Nysret Musliu, Andreas Pfandler, Reinhard Pichler, Stefan RÄummele, and Stefan Woltran.
- 2010 November
The November 2010 FPT Newsletter celebrates over 8 million euro in research grants, awards and prizes to the PC Community this year. Key article: Finding Topological Subgraphs is FPT (Grohe, Kawarabayashi, Marx, Wollan).
- 2010 June
The June 2010 FPT Newsletter announces a new online compendium by A. Perez. Key articles: Polynomial Lower Bounds for Kernels (Holger Dell), and Protein Structure Prediction (Xiuzhen Huang).
- 2009 September
This fully-packed Newsletter features articles by Georgia Kaouri, Michael Lampis and Valia Mitsou describing new directions in treewidth, continuing work reported at ISAAC, and an article by Serge Gaspers on new uses of measure and conquer for parameterized branching algorithms, and a bit of History and ILP by D. Marx. We have a report on the marvelous Corsica AGAPE Workshop by Anke Truss and Mathias Weller, and a report on Bangalore Meeting by Vankatesh Raman, and another New Ideas column by Mike Fellows. Great picture of Daniel Laksthanov winning $100.
- 2009 June
- 2009 April
- 2008 May
The May 2008 FPT Newsletter reports on the long-outstanding parameterized Directed Feedback Vertex Set that has been solved and the paper by Chen, Liu, Lu, O’Sullivan, and Razgon appears at STOC’08. Directed “Spanning Tree with Constraints” problems, such as Directed Maximum Leaf or Directed Spanning Tree, have solutions based on the methodology of reducing to bounded treewidth. The paper, ‘Minimum-Leaf Outbranching’, parameterized by the number of non-leaf vertices by Gutin, Razgon, and Kim appeared at AAIM’08 , and “Parameterized Algorithms for Directed Maximum Leaf Problems” by Alon, Fomin, Gutin, Krivelevich and Saurabh was presented at
ICALP’07.
Given a 2-CNF formula, is it possible to remove at most k clauses so that the resulting 2-CNF formula is satisfiable? This problem known as ‘Almost-2-SAT’, ‘Allbut- k-2-SAT’, ‘Minimum 2-CNF-Deletion’, or ‘2-SATDeletion’, now has an O(15k) algorithm due to Razgon
and O’Sullivan. The extended abstract appears at ICALP’08. The full version of the algorithm is available
at http://arxiv.org/abs/0801.1300. More on this and other results are in the Newsletter.
The May 2008 FPT Newsletter also has an article on "k-Local Search" by Daniel Marx and an article "Treewidth: History, Applications, Algorithms, and
Programs" by Hans Bodlaender.
- 2006 November
- 2006 May
- 2005 May
