The price of privately releasing contingency tables and the spectra of random matrices with correlated rows

By Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam D. Smith, Jonathan Ullman. 2010

119 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Tight Lower Bounds for Differentially Private Selection (2017, background): “Another line of work proves lower bounds in differential privacy via reconstruction attacks [13], [32], [33], [34], [35], [36], [37].”
Robust Traceability from Trace Amounts (2015, background): “, and t ≤ Ω(1 /α 2 ) , there exists an attacker Let D be a product distribution on [ − 1 , 1] d such that each marginal satisﬁes a technical smoothness condition (Deﬁnitions 6 and 27).”
A learning theory approach to non-interactive database privacy (2008, background): “[KRSU10] extend the lower bounds [DN03] from arbitrary subset-sum queries to hold also for an algorithm that only releases conjunctions.”
Fingerprinting codes and the price of approximate differential privacy (2013, background): “but apply only to certain families of queries. There have been attempts to prove optimal sample complexity lower bounds for k-way marginals. In particular, when kis a constant, Kasiviswanathan et al. [KRSU10] and De [De12] prove a lower bound of minfjQj1=2=;1=2gon the sample complexity. Note that wh”
Lower Bounds in Differential Privacy (2011, methodology): “A final goal considered herein, attribute privacy, has a more complicated description, but may be thought of as preventing blatant non-privacy for a single data attribute [12] in the presence of a certain kind of contingency table query.”
The Power of Linear Reconstruction Attacks (2012, methodology): “The bound on the norm appearing in the above theorem (asymptotically) matches that for adk×n matrix with independentτ -random entries (refer [22] for more details).”
Model Inversion Attacks that Exploit Confidence Information and Basic Countermeasures (2015, background): “Several authors have explored linear reconstruction attacks [10,12,23], which work as follows: given some released information y and assuming a hidden vector s of sensitive features (e.”
Differentially Private Online Learning (2011, unknown): “In a line of work started by [5] and subsequently explored in details by [12, 25], it was shown that if one answers O ( T ) subset sum queries on a dataset D ∈ { 0 , 1 T with noise in each query smaller than √ T , then using those answers alone one can reconstruct a large fraction of D .”
How to Use Heuristics for Differential Privacy (2018, background): “Since then, a number of algorithms and hardness re-sults have been given [UV10, GHRU13, KRSU10, TUV12, HRS12, FK14, CTUW14].”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “Next, we describe a more recent approach that was proposed by Kong and Valiant (2017). This method suffers from even higher variance, but it is computationally efficient.”
FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗ (2018, background): “The lower bound of Ω(1/α(2)) for k-way marginals is due to [40, 15].”
The power of factorization mechanisms in local and central differential privacy (2019, background): “sic lemma about diﬀerential privacy, which says that the variance of any diﬀerentially private algorithm for answering a single query w must be proportional to the sensitivity of the query. Lemma 26 ([KRSU10]). For any single-query workload w ∈ R|X|, and any data-independent mechanism M(h) = 1 nw ⊤h”