Aggregating inconsistent information: ranking and clustering

By Nir Ailon, Moses Charikar, Alantha Newman. Symposium on the Theory of Computing, 2005

317 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Large Language Models are Effective Text Rankers with Pairwise Ranking Prompting (2023, methodology): “Even though pairwise comparisons are not guaranteed to be transitive, we show robust empirical performance in the experiments, and leave applying methods with theoretical guarantees (Ailon et al., 2008; Bai and Coester, 2023) for future work.”
Trends in Cleaning Relational Data: Consistency and Deduplication (2015, unknown): “Since solving the ILP problem is NP-hard [3], a number of greedy approaches have been proposed [42, 3] that generally work in the following steps: (1) all records are randomly permuted; (2) each record x is either assigned to an existing cluster or a new cluster, according to a certain criterion, su”
Large-Scale Deduplication with Constraints Using Dedupalog (2009, unknown): “Our algorithm builds on the work of Ailon et al. [26], but is a strict generalization of their work.”
Smooth sensitivity and sampling in private data analysis (2007, unknown): “However, this median may be difficult to compute (it is NP-hard in, for example, permutation spaces [2]).”
A Short Introduction to Computational Social Choice (2007, unknown): “Its practical computation has also been addressed [36, 24], while other work has focussed on approximating Kemeny’s rule in polynomial time [3] .”