Title:	Computational Social Choice Research and Parameterized Complexity
Date:	April 29, 2009 (Wednesday)
Time:	10:30 a.m. - 11:30 a.m.
Venue:	Room 121, 1/F, Ho Sin-hang Engineering Building, The Chinese University of Hong Kong, Shatin, N.T.
Speaker:	Dr. Frances Rosamond Parameterized Complexity Research Unit Office of the DVC of Research The University of Newcastle Australia

ABSTRACT:

Shared decision making arises everywhere in modern society: in politics, economics, science and law. Large social networks supported by Web 2.0, electronic voting on videos, wikis, blogs, speeches by politicians, new hires, committee members and essentially anything, and electronic support of business processes and services require algorithms for consensus, judgment aggregation, ranking and negotiation.

Ranking algorithms used by search engines may also be useful for evaluating microarray data in bioinformatics, determining how to combine gene expression information with network structure from gene ontologies, or expression profile correlations. Algorithms for merging preference aggregation may also be used in multi-agent intelligent systems such as computerized air-traffic control where systems from neighbouring countries negotiate between themselves to track flights and recommend available runways, and in Learning Theory where consensus by motion sensors may help train robots to maintain balance and determine movement. Intelligent systems in management of risk and complexity, and trading strategies and auctions (eBay), place high demands on efficient protocols for consensus. Electronic voting requires new mechanisms for efficient, direct aggregation of preferences (referenda), and new ballot technology.

This talk describes some of the paradoxes in voting, outlines areas of computational social choice research, and gives parameterized complexity results for various election systems such as Kemeny, Young, and Dodgson under various parameterizations.

BIOGRAPHY:

Frances Rosamond works in the area of theoretical computer science, especially parameterized complexity and in particular, finding and proving kernelization rules, preprocessing rules that reduce the size of the original input. She received her Ph.D. from Cornell University. Dr. Rosamond came to the University of Newcastle from previous appointments at the University of Victoria, Canada; Victoria University of Wellington, New Zealand and was the founder and Chair of the Department of Mathematics and Natural Sciences at National University in San Diego, California. Rosamond is the editor of FPT News, the Parameterized Complexity Newsletter, and Administrator of the Parameterized Complexity WIKI which can be found at http://www.fpt.wikidot.com.

Enquiries: Miss Temmy So at tel 2609 8444

For more information, please refer to http://www.cse.cuhk.edu.hk/seminar