本研究旨在通过自适应挑选子集并收集偏好反馈，在 Plackett-Luce 模型下解决 PAC 排名问题，提出了新的 pivot trick 技巧，从而实现了在一定概率下识别 n 个项目的 ε- 最优排名，（m-1）/m 降低的样本复杂度和对称排名算法的阶无法提高的。

Oct, 2018

本研究重新审视了来自 Feige 等人的 1994 年的噪声信息计算问题，改进其上下界以更好地描述查询复杂性，并考虑了自适应采样和非自适应采样这两种情况。

Jun, 2023

本文研究了使用多项式逻辑模型下的 $l（l≥2$)$-wise$ ($l≥2$) 比较的积极 PAC top-k 排名（即 top-k 项目选择）和总排名问题，通过自适应地选择查询组并观察每个查询的最受欢迎项的嘈杂结果，我们要设计排名算法，使用尽可能少的查询来恢复 top-k 或总排名。

Jun, 2018

文中提出了一种基于序列或主动排名的算法，该算法基于嘈杂的成对比较将一组 n 个项目排名并将这些项根据其得分分成预先指定大小的集合；本文针对这种算法进行了分析，证明了在某些情况下具有最优性并且不需要任何假设，比如在参数模型下进行的排名。

Jun, 2016

本文研究了具有单调对手的前 K 名排名问题，在随机生成的比较图的基础上，统计学家的目标是根据半随机比较图中的成对比较，准确地确定前 K 名的首选项目。主要贡献是开发了一种加权的最大似然估计器，它在样本复杂度方面实现了接近最优的性能，最多有对数因子 (log^2 (n))，其中 n 是比较的项目数量。通过分析和算法创新的组合实现了这一目标。

Feb, 2024

研究了反馈弧集问题的算法，使用 n 个元素上的顺序形成的锦标赛作为输入，并考虑到噪声干扰，以最大似然的方式找到排名。

Jul, 2007

透过自适应调用两两比较来研究可能近似正确且公平（PACF）排名问题，目标是根据我们提出的公平目标函数找出一个（ϵ，δ）-PACF 排名。我们使用的目标函数要求最小化组的误差 lq 范数，其中组的误差是组内所有项误差的 lp 范数，p,q≥1。我们提供了群体不可见和群体感知算法，并分析了其样本复杂度。我们对真实数据集和合成数据集进行了全面的实验以补充我们的理论结果。

Feb, 2024

本研究旨在通过成对比较的数据形式，使用 Copeland 计数算法实现对 n 个项目的排序，使其具有计算效率高，鲁棒性强，接近信息论极限等特点，并将结果扩展到汉明距离度量下的近似恢复问题和任意错误要求条件下的恢复问题。

Dec, 2015

我们重新审视了 Karp 和 Kleinberg 的嘈杂二分搜索模型，其中我们有 n 个具有未知概率 pi 的硬币可进行翻转。硬币按递增的 pi 排序，我们希望找到概率以 ε 为间隔交叉目标值 τ 的位置。我们通过解决高概率行为和尖锐常数两个理论挑战，给出了一个成功率为 1-δ 的算法，其样本数量为 1/Cτ,ε * (lg n + O (log^(2/3) n * log^(1/3) * 1/δ + log * 1/δ))，其中 Cτ,ε 是可达到的最优常数。对于 δ > n^{-o (1)}，该算法接近最优，对于 δ<<1，它是首个在常数因子内接近最优的界限。

Nov, 2023

使用有噪声的查询计算具有错误概率的函数问题，给出了计算 OR 函数和 MAX 函数所需的期望查询次数，并在两个函数的上下界中对错误概率进行了更紧密的依赖。

Sep, 2023