Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample:
a pair of items in the wrong order. The goal is to identify ... more >>>