Technion
 
         Computer Science Colloquium
 
Time+Place : Tuesday 03/04/2012 14:30 room 337-8 Taub  Bld.
Speaker    : Professor Frances Rosamond
Affiliation: Charles Darwin University, Northern Territory, Australia.
Host       : Hadas Shachnai
Title      : Determining the Winner of a Dodgson Election is Hard
 
Abstract   :
In 1876 the mathematician Charles Dodgson (better known as Lewis Carroll)
formulated a rule that defines the winner of an election even if there is no
Condorcet winner. A candidate who beats every other candidate in pairwise
comparison is said to be a Condorcet winner. Unfortunately, an election may
have a cyclic structure (candidate a beats b, candidate b beats c and c
beats a), and therefore no candidate who beats all others in pairwise
comparison. The Dodgson Score measures how close a candidate is to being a
Condorcet winner. Candidates with a minimum Dodgson Score are the election
winners. As are many election methods, Dodgson Score is NP-hard. This talk
discusses the complexity of Dodgson Score in the parameterized framework. We
give a reduction from Multi-Colored Clique to show that Dodgson Score,
parameterized by the number of votes, is W[1]-hard.
 
Short Bio:
Professor Frances Rosamond received her PhD from Cornell University, Ithaca,
NY. Her research area in parameterized complexity focuses on kernelization
and computational social choice. Rosamond is Editor of the Parameterized
Complexity Newsletter, and Moderator of the Parameterized Complexity wiki
located at  <http://FPT.wikidot.com.> She is active in mathematical sciences
popularization and education, and offers workshops using activities and
materials from the program, "Computer Science Unplugged!" Frances Rosamond
is a research professor at Charles Darwin University, Northern Territory,
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>