Tight Lower Bounds for Differentially Private Continual Counting
本论文研究差分隐私中的持续计数（continual counting）问题：数据流逐步到达，算法需要为每个时刻持续发布满足差分隐私的前缀和近似结果。二进制树机制（Binary Tree Mechanism, BTM）是该问题的标准算法，但自
#lower-bounds
共收录 3 条相关情报。
← 返回所有主题Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks
本文研究差分隐私（DP）约束下的基础图优化问题，并给出基于“重构攻击”思路的新型下界证明。作者考虑图 G=(V,E,w⃗)，其中顶点集 V 与边集 E 是公开的，只有边权函数 w:E→ℝ 需要满足 ℓ1 邻接关系下的差分隐私。研究对象包括两
Multivalued Consensus: General Adversaries Require More Communication
本文研究多参与方容错共识问题，特别关注一般性（非阈值）对手模型下的通信复杂度下界。作者基于有限射影几何构造了一个无限族 Z_proj^{n,d} 的对手结构，该结构满足 Q^d 条件（即任意 d 个对手集合的并集不覆盖全部参与者）。对于这类