arXiv 论文提出可处理自适应线性查询的在线差分隐私算法

Aleksandar Nikolov 的论文研究在差分隐私约束下在线回答计数等线性查询，提出一种新算法，在实现多对数级竞争比的同时能处理自适应选择的查询。该结果说明，离线线性查询、 oblivious 选择的在线查询与自适应在线查询三者的最优误差界之间不存在大的分离。算法结合了此前的在线分解方法与新的分层欧氏迭代数据库构造，作者还给出下界，表明竞争比中某些多对数因子无法避免。