Consider the following learning problem. Alice picks a linear order over n elements, and Bob is trying to reveal it. They interact in rounds: in each round Bob proposes a linear order, and if his guess is incorrect, Alice returns a counterexample - a pair whose relative order is wrong.
How many rounds can Bob guarantee in the worst case? Does the answer change if the counterexamples are chosen uniformly at random? What can be said for more restricted families of linear orders? For example, suppose the elements are embedded as points x₁,…,xₙ in ℝᵈ, and the order is determined by their distances to an unknown point x*.
We will discuss these questions, present solutions to some of them, and describe several open problems and partial results.
Based on ongoing joint work with Noga Alon and Shlomo Moran, and on a COLT 2026 paper with Mark Braverman, Roi Livni, Yishay Mansour, and Kobbi Nissim.