First CS colloquium talk of the 2007 year

Today's talk at U of T CS is on How To Rank with Few Errors by Claire Kenyon-Mathieu from the CS dept. in Brown University.

Here's the abstract of the talk:

Suppose you ran a chess tournament, everybody played everybody, and you want to use the results to rank everybody. Unless you were really lucky, the results will not be acyclic, so you cannot just sort the players by who beat whom. A natural objective is to find a ranking that minimizes the number of upsets, where an upset is a pair of players where the player ranked lower on the ranking beats the player ranked higher. We review heuristics, algorithmic and hardness results for this problem, focusing on recent advances; we also discuss applications to voting theory and to rank aggregation.

This seems to be an interesting talk about ranking, I wonder if there's any use of this in PhD thesis. Probably not, but still it's good to learn about other things not related to your area. Like when I attended the talk about how to interview for a faculty position, it's good to attend these presentations to see how the speaker presents, the flow, the type of slides, you learn a lot from these talks (even though technically it's probably beyond what I want to know). And these talks challenge me to think, to absorb, so I keep on the ball with what is happening in Computer Science.

Claire is now starting the talk. There is lots of research and information on rank aggregation like an election or a vote, like meta-search engines. The problem is how to aggregate into a single "good" ordering. We would like to have properties for ranking, like if every voter prefers a to b, then the output ordering should also be a before b. We also want to have an extended Condorcet principle, therefore the problem is an optimization problem called the Kemeny-optimal aggregation which is the only function that is neutral, consistent and satisfies the extended Condorcet principle. The rank ordering is the Kemeny-optimal aggregation which minimizes the average Kendall-tau distance to input orderings, where the Kendall-tau distance is the number of pairs of orderings in disagreement.

However, this problem is NP-hard so what we can do is to use heuristics and use an approximation algorithm. She is now talking about a chess tournament where every chess player plays everybody else. This translates to making a tournament to become acyclic. She's talking about algorithms analysis, it's getting extremely theoretical, and since I'm not a theoretical computer science person, she's tuned me out.

On Technorati: rank aggregation