WELCOME to the PARAMETERIZED COMPLEXITY COMMUNITY WIKI.
The field is growing by leaps and bounds—Herein you will find applications, open problems, the 'FPT Races' Table, the FPT Newsletter, and resources including courses about parameterized complexity and open positions. Read the "Quick Summary of Parameterized Complexity - 2012".
The 7th International Symposium on Parameterized and Exact Computation IPEC2012 will be part of ALGO, which also hosts ESA (Sept 10-12), WABI, WAOA, ATMOS, and ALGOSENSORS. IPEC covers research in all aspects of parameterized and exact algorithms and complexity. Location is Ljubljana, Slovenia.
Important Dates:
Abstract registration: June 20, 17:00 GMT
Paper submission: June 23, 17:00 GMT
Notification of acceptance: July 15
Symposium: September 12-14
Invited Speaker: Martin Grohe (Berlin, Germany)
Excellent Student Paper Awards may be awarded by the Program Committee to one or more papers accepted to the symposium. A paper is eligible for the award if all authors are students at the time of submission, where a student is someone who has not been awarded a PhD.
NEWS: The "AND-Conjecture solved!! See 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. Andrew Drucker, MIT, has new results.
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.
