[Colloquium] Reminder : Guest Speaker @ TTI-C (Newman -TODAY 1/30@10:00am)

[Katherine Cumming]

TTI-C Guest Speaker
 
Presented by:  Toyota Technological Institute at Chicago
 
Speaker: Alantha Newman, The Max Planck Institute
Speaker's home page: http://www.mpi-inf.mpg.de/~alantha/
 
 
Date: Monday, January 30, 2006 
Location: TTI-C Conference Room
Time:  10:00 am
 
Title:
 
Aggregating Inconsistent Information: Ranking and Clustering
 
Abstract::
 
A ranking of n web pages is to be chosen from outputs of k search engines.
How do we choose one ranking minimizing the "disagreement" with the k
rankings?
 
A clustering of n genes is to be chosen from outputs of k clustering
algorithms. How do we choose one clustering minimizing the "disagreement"
with the k clusterings?
 
These information aggregation problems date back to 1785, when the French
philosophers Condorcet and Borda considered voting systems in which each
voter specifies a full ranking of a set of candidates. Recently, their
algorithmic and complexity aspects have been studied.
 
We obtain improved algorithms for both these problems using a remarkably
simple principle. Our techniques also apply to related graph optimization
problems such as the minimum feedback arc set problem on tournaments and the
correlation clustering problem on complete graphs. Additionally, we show
that the problem of finding a minimum feedback arc set on tournaments has no
polynomial-time algorithm, assuming NP is not contained in BPP. This almost
settles a long-standing conjecture of Bang-Jensen and Thomassen that the
problem is NP-hard.
 
This is joint work with Nir Ailon and Moses Charikar. 
 
----------------------------------------------------------------------------
------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.   
For information on future TTI-C talks and events, please go to the TTI-C
Events page:  http://www.tti-c.org/events.html.  TTI-C (1427 East 60th
Street, Chicago, IL  60637)
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060130/62328cdb/attachment.htm