Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries

• URL: http://arxiv.org/abs/2609.02880v1
• Date: Wed, 02 Sep 2026 17:56:39 GMT
• Title: Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries
• Abstract summary: We provide a randomness-efficient analog of the $| cdot |_K$-norm mechanism of Hardt and Talwar.<n>For the $ell_infty$-error, our algorithm can answer $d$ linear queries with $O(d / varepsilon)$ error using $O(log d)$ random bits.
• Score: 37.158613306509956
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Private Continual Counting of Unbounded Streams [11.941250828872189]
  We study the problem of differentially private continual counting in the unbounded setting where the input size $n$ is not known in advance.<n>Using the common doubling trick' avoids knowledge of $n$ but leads to suboptimal and non-smooth error.<n>We introduce novel matrix factorizations based on logarithmic perturbations of the function $frac1sqrt1-z$ studied in prior works.
  arXiv  Detail & Related papers  (2025-06-17T23:09:53Z)
• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
  We give the first sublinear space differentially private algorithms for the fundamental problem of counting distinct elements in the turnstile streaming model.<n>Our result significantly improves upon the space requirements of the state-of-the-art algorithms for this problem, which is linear.<n>When a bound $W$ on the number of times an item appears in the stream is known, our algorithm provides $tildeO_eta(sqrtW)$ additive error using $tildeO_eta(sqrtW)$ space.
  arXiv  Detail & Related papers  (2025-05-29T17:21:20Z)
• Differentially Private Set Representations [13.576656322669098]
  We study the problem of differentially private (DP) mechanisms for representing sets of size $k$ from a large universe.<n>Our first construction creates $(epsilon,delta)$-DP representations with error probability of $1/(eepsilon + 1)$ using space at most $1.05 k epsilon cdot log(e)$ bits.<n>We also present a second algorithm for pure $epsilon$-DP representations with the same error using space at most $k epsilon cdot log(e)$ bits
  arXiv  Detail & Related papers  (2025-01-28T03:29:00Z)
• Differentially Private Approximate Pattern Matching [0.0]
  We consider the $k$-approximate pattern matching problem under differential privacy. The goal is to report or count allimate variants of a given string $S$ which have a Hamming distance at most $k$ to a pattern $P$. We give 1) an $epsilon$-differentially private algorithm with an additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) an $epsilon$-differentially private algorithm with an additive error $O(epsilon-1
  arXiv  Detail & Related papers  (2023-11-13T15:53:45Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2021-11-09T16:50:18Z)
• Testing Boolean Functions Properties [1.5924410290166868]
  The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is $varepsilon$-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm.
  arXiv  Detail & Related papers  (2021-09-14T15:27:38Z)
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
  We give an algorithm for this task that achieves an expected $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$. On the other hand, the algorithm of Dagan and Kur has a remarkable advantage that the $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$ holds not only in expectation but always.
  arXiv  Detail & Related papers  (2020-12-16T17:58:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Fast digital methods for adiabatic state preparation [0.0]
  We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error.
  arXiv  Detail & Related papers  (2020-04-08T18:00:01Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits [13.32560004325655]
  We consider an adversarial variant of the classic $K$-armed linear contextual bandit problem. Under the assumption that the $d$-dimensional contexts are generated i.i.d.at random, we develop efficient algorithms based on the classic Exp3 algorithm.
  arXiv  Detail & Related papers  (2020-02-01T22:49:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.