该论文研究了自适应数据分析（Adaptive Data Analysis, ADA）中的基本问题：随机性是否必要？ADA 问题形式化了在数据集被重复使用时防止虚假发现和过拟合的挑战。输入是一个包含 n 个独立同分布样本的数据集，来自未知分布 P，目标是回答 k 个自适应选择的统计查询。主要问题是如何支持尽可能多的查询（即 k 多大），主要取决于样本数 n。先前工作已充分理解了随机化机制：存在计算高效的机制支持 k ≈ n^2 个查询，且没有计算高效机制能回答 k >> n^2 个查询。然而，随机性是否必要？尽管 ADA 研究已进行十年，该问题仍未解决。一个早期观察是，当分析师计算能力受限时，随机性不是必需的。但对于计算能力无界的分析师，随机性的必要性仍未知。本文的主要贡献是在信息论随机预言机模型中解决了这一差距。令人惊讶的是，论文证明随机性是严格必要的：当分析师无界时，任何确定性机制在仅 k = O~(n) 个查询后就会失败。这表明随机化在抵御无界分析师的自适应查询中扮演关键角色。结果适用于理论计算机科学、数据隐私和机器学习中的自适应数据分析场景。适合理论研究者、密码学及差分隐私领域从业者阅读。