The algorithm can answer linear queries with differential privacy using few (expected) random bits using $O(d / \varepsilon)$ error using $O(\log d)$ random bits, improving upon algorithms of Canonne et al. and Ghentiyala.
Abstract
We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the $\| \cdot \|_K$-norm mechanism of Hardt and Talwar [HT10]. For the $\ell_\infty$-error, our algorithm can answer $d$ linear queries with $O(d / \varepsilon)$ error using $O(\log d)$ random bits, improving upon algorithms of Canonne et al. and Ghentiyala [CSV25, Ghe26]; this is optimal when $\varepsilon \le 1/d$. We also provide a computationally efficient version of our algorithm, albeit with an $O(\log d)$ multiplicative increase in the error.
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected...
Yong-Gang Jiang, Xiao-Ming Sun, Peng-Hui Yao et al.· 0 citations
We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length $n$, information-theoretic protocols require $\Omega(\sqrt{n})$ error under pure differential privacy and $\Omega(\sqrt{n}/\log n)$ error under s...
A $\Omega(\log\log n) bit lower bound for the constant error-rate regime, and a $\Omega(1/\delta)$ bit lower bound for arbitrarily small error rates, as well as a tight one-way protocol using $O(\log\log n + \log(1/\delta))$ bits of communication.
A multiplicative-adversary derivation that tracks the progress produced by individual oracle queries and proves that unique OR on bits with success probability $1/2+\zeta$ requires $\Omega(\sqrt{\zeta n})$ queries, and reduces unique OR to the two-weight counting problem.
Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we sho...
Keshav Bhateja, Mehdi Esmaili, A. Mantri· 0 citations
We study non-adaptive bit-probe schemes for static set membership. Each query reads a fixed number of bits and answers by strict majority. We revisit the random bipartite-graph construction of Garg and Radhakrishnan [STACS, 2017]. The main observation is that a slightly stronger expansion property already bounds the nu...
Mirza Galib Anwarul Husain Baig, Aman Kumar, Pawan Kumar Saw et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
