我们重新审视了 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

这篇论文探讨了用边缘检测查询学习一般图的问题，研究并给出了 Las Vegas 算法和 Monte Carlo 算法不同的轮数和查询数量，概述了解决此问题的难点和限制。

Mar, 2018

在这篇研究论文中，我们考虑了最近由 Banerjee 等人（2022）提出的预测图搜索问题。我们设计了一种算法来应对未知图上的搜索任务，并且在预测误差上提供了最优或接近最优的算法依赖关系的保证。此外，我们还提出了 Banerjee 等人（2022）算法在已知图上的性能边界，并为该情景建立了新的下界。

Feb, 2024

研究二元马尔可夫随机场中，图形选择问题在高维情况下的信息论局限性，为具有最多 k 条边的 p 个定点图的类 $Gpk$ 以及最高 degree 不超过 d 的 p 个定点图的类 $Gpd$，提出了正确图形选择的必要和充分条件，并建立了一个图形译码器，该译码器适用于样本量 n>c'k² log (p) 和 n>c'd³ log (p)。

May, 2009

本文研究了随机匹配问题，提出一种能够提高精度的探测边的新方法和其在最大化构建匹配的期望收益中的应用，尤其在求解在线偏二分图情况时取得了显著提升。

May, 2015

本研究研究了一种随机图模型和匹配问题，提出了基于线性规划和贪心的近似算法，并探讨了匹配问题在肾脏交流和在线广告上的应用。

Aug, 2010

本文研究了一个叫做广义二分搜索的算法，通过一系列策略性的查询确定二值函数，提出了新的不连贯性和几何条件，证明其信息理论最优查询复杂度。此外，该算法还应用于学习半空间问题。

Oct, 2009

提出了一种组合优化模型，可以在限定次数的查询下寻找图中两点的连通性，创新性地提出了一种较为可扩展的精确算法以及适用于大规模数据的启发式算法。

Feb, 2023

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

Jun, 2023

探究搜索者搜索未知的加权无向图的问题，证明最近邻算法的竞争比率在树中为 θ(logn)，并研究参数范围内算法 Blocking 在单轮图上是 3-competitive，在仙人掌图上是 5/2+√2 约等于 3.91-competitive。

Apr, 2020