Jul, 2016

非交互式联合分布模拟的可决定性

PDF
TL;DR通过分析布尔函数的性质，本研究得出当一个分布是有限域上的分布且另一个是 $2×2$ 分布时，非交互模拟问题是可判定的，并且可以借助不变性原理和正则化引理来确定样本数的收敛边界。
发现论文，激发创造
  • 相关分布的非交互式模拟可判定

    该研究利用高斯几何和新的平滑策略，证明了对于任何有限字母表，可以在没有交互的情况下模拟 Alice 和 Bob 的分布 Q，这解决了一个关于信息论的基本问题。

    Jan, 2017

  • 分布式仿真和分布式推断

    研究了一个关于 “simulate-and-infer” 的通信受限问题，在只要求每个参与者发送少于 log k 比特给中央仲裁者的情况下，寻找利用最少的参与者，对未知概率分布进行推断的最优策略，表明了 simulate-and-infer 策略是最优采样复杂度的，并提出了一个有效的公共硬币通信协议，可以突破身份测试的通信复杂度下界。

    Apr, 2018

  • 测试离散分布的条件独立性

    研究了离散分布的条件独立性检验问题，并给出了样本复杂度的上下界，提出了第一种具有次线性样本复杂度的条件独立性测试器，用于对分布属性进行测试。

    Nov, 2017

  • 高概率离散分布的最佳测试

    研究总变差距离下的离散分布测试问题，提出可用于样本较高概率区域的属性测试的算法，包括相应参数的样本复杂度与正确性保障。

    Sep, 2020

  • 最优样本本地隐私假设选择和互动的可证优势

    我们研究了局部差分隐私约束下的假设选择问题，设计了一种使用较少样本的 ε- 局部差分隐私算法来选择假设，该算法的样本复杂度趋近于最优，并且通过定义关键查询的概念为统计查询算法提供了一种新的方法。

    Dec, 2023

  • 本地差分隐私中交互性的作用

    研究在局部差分隐私中互动性的作用：分类、转换和假设检验问题。

    Apr, 2019

  • 非同分布样本的测试

    在非独立同分布的样本情况下，研究子线性样本属性测试和估计在哪些情形适用；给定一组分布，考虑学习或测试平均分布的属性，在某些情况下需要 $\Theta (k/\varepsilon^2)$ 样本；对于均匀性或相似性的测试，给定 $c=1$ 个样本，需要线性数量级的 $k$ 样本；$c \geq 2$ 时，恢复了独立同分布的亚线性样本测试，需要 $O (\sqrt {k}/\varepsilon^2 + 1/\varepsilon^4)$ 样本，且在 $c=2$ 的情况下，即使是线性数量级的 $\rho k$ 样本，也不能进行均匀性测试。

    Nov, 2023

  • 关于条件概率的可计算性

    研究概率论基础中的条件概率可计算性，并证明了存在无法计算的条件概率分布，从而排除了概率推断的通用算法存在的可能性，但在许多常见建模情况下仍然可以进行概率推断。

    May, 2010

  • 通过量子干涉实现无冲突联合采样以满足偏好

    本研究探讨了几种采样方法，这些方法可收敛到启发式联合选择概率矩阵，满足玩家的偏好，从而显著降低了计算成本和保密性问题。特别地，我们通过光子的量子干涉介绍了两种无冲突联合抽样方法，第一个系统允许玩家在具有相同偏好时隐藏其选择，第二个系统则通过信任的第三方假设遮蔽了玩家的选择。

    Aug, 2022

  • 关于离散分布的量子与经典可学习性

    本文比较了传统和量子学习者在 Probably Approximately Correct (PAC) 框架下的生成模型能力，并构造了一类离散概率分布，通过决策 Diffie-Hellman 假设证明传统生成模型算法无法高效 PAC 学习，但我们构建了一个高效的量子学习器。同时，本文还讨论了证明经典生成建模难度结果的技术，以及布尔函数和离散概率分布的 PAC 学习性之间的关系。

    Jul, 2020