Suppose we want to rank a group of chess players based on a collection of matches played between a pair of players. A natural objective is to maximize the fraction of matches in the collection whose outcome was consistent with the ranking --- the winner is the higher ranked player.

This is exactly the Maximum Acyclic Subgraph problem and has been extensively studied in the purview of approximation algorithms. Despite much effort, the best algorithm known satisfies only a half of the matches played. On the other hand, even a random ranking of the players is consistent with half the matches in expectation. In this talk, I will describe why it may be NP-hard to beat the guarantees of the random ranking algorithm.

This talk is based on work with my collaborators: Moses Charikar, Venkatesan Guruswami, Johan Håstad, and Prasad Raghavendra.