Sorting from Counterexamples

Noga Alon, Shay Moran, Shlomo Moran

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 confirmatio…