Preprint
Aug 2026
Sorting from Counterexamples
The optimal query complexity up to constant factors is determined: while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$.
Noga Alon, Shay Moran, S. Moran
· 0 citations