在存在错误反馈的排序中，用最少次数找出正确顺序。
Sorting from Counterexamples
- 用几何方法表示排列，结合格伦鲍姆定理设计鲁棒排序算法。
- 噪声存在时，查询复杂度为 Θ(n log n + nk)，每条错误反馈增益约 n 次查询。
- 适用于有低维几何结构的排序任务，适合对噪声敏感的推荐系统场景。
考虑学习未知线性排序的问题：每轮学习者猜测一个完整排序，收到确认或反例（一对顺序错误的元素）。目标是以最少查询识别真实排序。研究当最多 k 个反例可能不真实且 k 未知时的情况。确定了最优查询复杂度至常数因子：Θ(n log n + nk)。无噪声时复杂度与经典排序一致，每个不真实反例带来约 n 的额外开销。上界基于排列的几何表示和格伦鲍姆定理，下界结合排序论证与康多塞型构造。此外，研究目标排序具有低维几何表示的情形：每个项目对应 ℝᵈ 中一点，排序由投影到未知方向获得。给出上界 O(d² log n + dk) 与下界 Ω(d log n + dk)，噪声项差距仍存，噪声无关项差一因子 d。
原文摘要 · Abstract (English)
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 the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $Ω(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。