Complexity of Differentially Private Selection via Federated APIs
Differential privacy (DP) has become the standard for privacy-preserving data analysis, yet its practical implementation
#cs.DS
共收录 54 条相关情报。
← 返回所有主题Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy
We study learning a discrete distribution under person-level differential privacy in the batched setting. Given $n$ user
Private Evaluation of High-Dimensional Functions
We study differentially private black-box evaluation of arbitrary high-dimensional functions. Given a dataset $S$ and qu
Subgraph Counting with Local Node Differential Privacy
We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introd
Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
We propose a general framework for non-interactive locally differentially private (LDP) learning of structured univariat
Fast Forgiving Base64 Decoding with SIMD Instructions
On the Internet, we use the Base64 format to represent binary data (e.g., images or cryptographic keys) as text. The ES2
Can Rényi Accountants Beat Lossless Accountants for DP-SGD?
Recent frameworks in differential privacy (DP), such as privacy loss distributions and $f$-DP, provide lossless represen
Local Sensitivity in Exponential Selection: Failure Modes and Valid Calibrations
Selection is a task that chooses one element from a finite public candidate range to maximize a data-dependent score. In
BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height
Finding heavy nodes in a tree---those whose counts exceed a given threshold---is a building block for analysis and learn
When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT
Byzantine quorum safety relies on correct replicas refusing to sign conflicting values. A replica that loses its protoco
Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
该论文研究 F_3^n 上的向量子集和问题：给定 m 个取自 F_3^n 的随机向量，要求找出一个非空子集使其向量和为零；m 越小，问题越难。该问题与后量子密码（尤其是基于 LWE 的构造）以及组合优化密切相关，也是量子优势研究中的经典试验
Verifiable quantum advantage based on polynomials with planted structures
该论文研究的是量子优势（quantum advantage）理论中的一个核心开放问题：是否存在一类量子优势协议，其资源需求与随机电路采样（random circuit sampling, RCS）相当，同时又能仅凭量子计算输出的经典数据被经
MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One
该论文提出了一种名为 multitable 的新型哈希表结构，并给出了 Rust 参考实现。作者要解决的核心问题是：现有主流工程实现（以 Rust 生态中 hashbrown 所采用的 SwissTable 为代表）在物理负载因子上受到刚性
Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold
该论文研究一个源自密码学理论的基础问题：关于哈希函数的结构性知识，能否加速对它的黑盒碰撞检测？作者从「实例最优性」（instance optimality）这一超越最坏情况分析的极端标准切入。实例最优性要求存在单一算法，使其在每一个具体输入
Geometry-Adaptive Mechanisms for Private Synthetic Data
该论文研究的是差分隐私（DP）合成数据生成中的效用保证问题，具体以 1-Wasserstein 距离作为效用度量。背景与核心问题：对定义在 [0,1]^d（d≥2）、样本量为 n 的数据集，已有纯 ε-差分隐私机制所能达到的期望 1-Was
The planted tensor problem over finite fields: algorithms and cryptography
本文受随机图上经典的植入团（planted clique）问题启发，把这一平均情形复杂性范式推广到有限域上的张量，提出「植入式完全迷向空间问题」（planted totally-isotropic space problem）。设定如下：令
An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting
本笔记是一篇数学论证性的综述/讲解文章，作者 Jalaj Upadhyay 针对差分隐私（DP）持续计数（continual counting）问题的下界证明，给出了尽可能详尽的推导说明。所谓持续计数，是指在数据流持续到达的场景下，每一次到
Tight Lower Bounds for Differentially Private Continual Counting
本论文研究差分隐私中的持续计数（continual counting）问题：数据流逐步到达，算法需要为每个时刻持续发布满足差分隐私的前缀和近似结果。二进制树机制（Binary Tree Mechanism, BTM）是该问题的标准算法，但自
Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures
该论文研究的是差分隐私合成测度（differentially private synthetic measure）的效用上界问题，属于差分隐私与最优传输/高维统计交叉的理论工作。作者考虑最坏情况数据模型：给定 [0,1]^d 空间中的 n
Private Graph Property Testing
该论文研究的是「差分隐私图性质测试」这一此前几乎空白的交叉方向。图性质测试（graph property testing）的基本问题是：给定一个规模极大的图，能否只做亚线性（sublinear）次数的查询，就判断它满足某个性质，还是与满足该