{"id":"arxiv/2608.21579","url":"https://arxiv.org/abs/2608.21579","tags":["cs.LG","cs.CC","cs.CG","cs.DS","math.CO"],"score":0,"title":"Sorting from Counterexamples","domain":"cs.LG","source":"arxiv","authors":["Noga Alon","Shay Moran","Shlomo Moran"],"reviews":0,"subject":"cs.LG","summary":"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 the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \\[ Θ(n\\log n + nk). \\] Thus, while the noiseless complexity matches…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-21","reactions":{}}