Technion
 
         Computer Science Colloquium
 
Time+Place : Tuesday 27/03/2012 14:30 room 337-8 Taub  Bld.
Speaker    : Prof. Michael Fellows
Affiliation: Charles Darwin University, Australia.
Host       : Johann Makowsky
Title      : Parameterizing on the Number of Numbers
 
Abstract   :
There are many results in computational complexity about ''weighted
problems''
and these weighted versions of problems generally have stronger claims to
modeling realistic inputs. Yet, combinatorial optimization problems enriched
by arbitrary weights tend to be even harder (in classical complexity terms)
than their unweighted versions, especially if the weights are presented in
binary. But where do the weights come from? Do binary weights make any
realistic sense in any combinatorial optimization problem to be viewed in
terms of computational complexity? The talk will describe some initial
investigations in the parameterized complexity framework, parameterizing by
the number of numbers. The talk will also hope to provoke some discussion
about realism in the modeling of weighted combinatorial optimization
problems.
 
(Joint work with Serge Gaspers and Frances Rosamond)
 
Short Bio:
Professor Fellows received his PhD from the University of California, San
Diego, in 1985 and has since taught at universities in the USA, Canada, New
Zealand and Australia. In 2006 he received the prestigious Humboldt Research
Award for his foundational work on parameterized complexity. The first book
in the area, Parameterized Complexity, with Rod Downey of Victoria
University in Wellington, based on their papers in the 1990's, has been
cited more than 2,000 times, and the field has developed into a vigorous
branch of contemporary theoretical computer science having strong
applications in such areas as Bioinformatics and Artificial Intelligence.
Professor Fellows is an Associate Editor of the ACM Transactions on
Algorithms and of the Journal of Computer and System Sciences. He has
contributed to a number of areas, including Cryptography, Bioinformatics,
Network Mapping, Computational Social Choice and Computer Science Education
for the Elementary Grades. His work has been cited more than 8,000 times
altogether. Professor Fellows is currently an Australian Professorial Fellow
at Charles Darwin University in Darwin, Australia.
 
Refreshments served from 14:15 on,
 	Lecture starts at 14:30
 
----------------------------------------------------------
Visit our home page-   <http://www.cs.technion.ac.il/~colloq>
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Hadas Heier   <heier@cs.technion.ac.il>