Hajiaghayi Wins 2015 Nerode Prize

Mohammad T. Hajiaghayi, an associate professor of computer science with an appointment in UMIACS, will receive the 2015 European Association for Theoretical Computer Science (EATCS) Nerode Prize, which is awarded annually for outstanding papers in the area of multivariate algorithmics.

Hajiaghayi was recognized for a paper he co-authored in 2005, "Subexponential Parameterized Algorithms on Bounded-Genus Graphs and H-Minor-Free Graphs,” which was published in the Journal of the ACM.

The paper, written by Hajiaghayi, Erik Demaine, Fedor Fomin and Dimitrios Thilikos, introduced a new framework for designing fixed-parameter algorithms. The results can be applied to a broad family of graph problems, called bidimensional problems, which includes many domination and covering problems such as vertex cover, feed-back vertex set, minimum maximal matching, and more. The paper and the theory in it was the topic of Hajiaghayi's doctoral thesis.

The EATCS Nerode Prize, first awarded in 2013, is named in honor of Anil Nerode for his major contributions to mathematical logic, theory of automata, computability and complexity theory. Any research paper, or series of research papers, by a single author or by a team of authors published in a recognized refereed journal are eligible for the award. The papers should have been published at least two years, and at most 10 years, before the year of the award nomination.

Hajiaghayi will receive the award at ALGO 2015, an annual event combining the premier algorithmic conference European Symposium on Algorithms (ESA) and a number of other specialized conferences and workshops, and also give a talk on the paper. The event will be held Sept. 16–18 in Patras, Greece.