Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I am looking for references for the following problem, which I feel must have been studied before. I have n items and I want to rank them. I randomise once at the beginning of the process and then for each pair of items I have an x% chance of getting the right ordering, let us say independently. I then use these comparison results to rank the items. I would like to know how good/bad the ranking can be given unbounded computation and also any methods for finding a good ranking in reasonable time. Let us also say that there is a true total ordering under the hood.

I am aware of some of the literature on binary sorting with errors but the papers I found, at least, seem to answer a different set of questions.

share|improve this question
For adversarial errors see cstheory.stackexchange.com/questions/423/… . –  Warren Schudy Nov 11 '10 at 22:13
add comment

1 Answer 1

up vote 10 down vote accepted

If I understand your question correctly it is answered in Braverman and Mossel's "Sorting with Noisy Information" http://arxiv.org/PS_cache/arxiv/pdf/0910/0910.1191v1.pdf (see also conference version titled "Noisy Sorting without Resampling" IIRC.)

share|improve this answer
This is an excellent reference, which answers the question as I interpreted it. It also mentions the query complexity, which requires $O(n\log(n))$ (possibly erroneous) comparison queries. –  Derrick Stolee Nov 12 '10 at 3:01
Thanks very much Warren. I think that is the perfect paper for me to be getting on with. –  Raphael Nov 12 '10 at 8:30
A longer term link: arxiv.org/abs/0910.1191 –  András Salamon Nov 12 '10 at 10:07
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.