A Sieve-Accelerated Quadrature Method for Exact Privacy Accounting in the 2020 U.S. Decennial Census
2020年美国人口普查局采用了差分隐私技术保护数据隐私，通过向发布的普查表格注入整数值高斯噪声来实现。准确评估这些数据发布的隐私保证，可以使普查局确定满足给定隐私预算所需的最小噪声量，避免注入不必要的过多噪声，从而显著提高下游应用（如联邦资
#cs.DS
共收录 54 条相关情报。
← 返回所有主题On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA
本文研究高维差分隐私（DP）下的协方差矩阵估计和主成分分析（PCA）问题，重点关注协方差矩阵的k-行-列稀疏性（k-RCS）假设。在非私有设置中，已知仅需poly(k, log d)个样本即可解决这两个问题。然而，在DP设置下，现有的最好结
Differentially Private Submodular Maximization with a Knapsack Constraint
本文研究了在背包约束下进行子模最大化的差分隐私问题（SMK），这是离散优化中的基础问题，广泛应用于机器学习等领域。随着这些应用涉及越来越多的敏感个体数据，对具有形式化隐私保证的高效用算法需求日益增长。本文考虑了单调和非单调目标函数。对于单调
Differentially Private Hierarchical Heavy Hitters
本文提出并研究了在差分隐私保护下释放层次重击者（Hierarchical Heavy Hitters, HHH）的问题。层次重击者是经典重击者问题的推广，最早由Cormode等人在VLDB 2003中引入，用于在数据流中识别在层次结构上显著
Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory
本文研究动态有序集合（支持插入、删除、成员查询、前驱后继、最小值最大值等操作）的回顾性审计问题。集合由不可信方维护，被动审计者（auditor）仅需存储 5 个机器字和 1 个标志位，并在每次操作时接收一个常量大小的公开 tally 记录。
A Fast Gaussian Mechanism under Continual Observation, with Applications
本文研究持续观察下私有化发布k维向量更新的问题。初始向量为零向量，在时间点t_i上通过添加x^{(i)}进行更新，其中t_i∈[T]，x^{(i)}在k维单位球B_k内。两个数据集被认为是相邻的，如果它们的对称差大小不超过1。持续发布需要在
Uncertainty Principles for the Number Theoretic Transform
该论文研究了数论变换（NTT）的不确定性原理，并证明了在某些素数条件下，非零函数与其NTT变换的支撑集大小之和至少为q+1（q为给定素数，p为满足p≡1 mod q的素数）。这意味着一稀疏函数（k-稀疏）的变换支撑集至少为q-k+1。进一步
Differentially Private Range Subgraph Counting
本文首次研究了差分隐私下的范围子图计数问题（DPRSC）。子图计数是图分析中的基本问题，传统方法通常计算整个图中特定模式的出现次数。然而，实际应用常需对由多维属性范围选中的顶点诱导子图进行查询，同时保护隐私。差分隐私子图计数面临重大挑战：子
Multi-Objective Submodular Maximization with Differential Privacy
本文研究差分隐私（DP）约束下的多目标子模最大化（MOSM）问题，旨在从敏感数据集中选择一个最多包含 k 个元素的子集，以最大化 d 个单调子模函数的最小值，同时满足 ε-差分隐私。虽然差分隐私单目标子模最大化和非隐私的多目标子模最大化已有
Optimal Rates for Differentially Private Hypothesis Testing with E-values
该论文研究了在差分隐私约束下，使用e值进行假设检验时的最优速率问题。E值作为一种灵活的工具，近年来在允许任意有效和自适应数据分析中受到广泛关注，其应用常涉及隐私或敏感数据。作者提出了一个核心问题：给定两个分布P和Q，在满足ε-差分隐私的e值
Privately Estimating Monotone Statistics in Polynomial Time
该论文研究差分隐私下单调统计量的高效估计算法。单调统计量指随着新观测数据增加而单调变化的统计量（如分位数、累积分布函数等）。传统方法采用子采样-聚合（subsample-and-aggregate）框架：将数据集分成多个子块，分别计算统计量
Near-Optimal Generalized Private Testing
该论文研究了差分隐私（DP）中的广义私有测试问题，该问题由 Liu 和 Talwar 在 STOC 2019 中提出。给定一个数据集 X 和一个序列的黑盒 ε_t-DP 机制 M_t，分析者需要以 DP 方式接受第一个成功概率 p_t =
Module Lattice Security (Part III): Structured CVP Distance on the Log-Unit Lattice
本文是'模格安全性'系列论文的第三部分，聚焦于分圆域Q(ζ_{2^k})的对数单位格上的结构化最近向量问题（CVP）距离。论文首先证明了从随机短环元素到对数单位格的L^2 CVP距离渐近收敛到(π/(2√6))√n，其中n=2^{k-1}。
Variational and Majorization Principles in Lattice Reduction
本文从变分与优化原理的角度重新审视格约简（Lattice Reduction）中的核心机制。格约简通过局部交换操作（如 Lovász 交换）平滑 Gram-Schmidt 轮廓，作者使用 majorization（优化）理论精确刻画了这一过