|
 ABSTRACT
This work is at theintersection of two lines of research. One line, initiated by Dinurand Nissim, investigates the price, in accuracy, of protecting privacy in a statistical database. The second, growing from an extensive literature on compressed sensing (see in particular the work of Donoho and collaborators [4,7,13,11])and explicitly connected to error-correcting codes by Candès and Tao ([4]; see also [5,3]), is in the use of linearprogramming for error correction. Our principal result is the discovery of a sharp threshhold ρ*∠ 0.239, so that if ρ < ρ* and A is a random m x n encoding matrix of independently chosen standardGaussians, where m = O(n), then with overwhelming probability overchoice of A, for all x ∈ Rn, LP decoding corrects ⌊ ρ m⌋ arbitrary errors in the encoding Ax, while decoding can be made to fail if the error rate exceeds ρ*. Our boundresolves an open question of Candès, Rudelson, Tao, and Vershyin [3] and (oddly, but explicably) refutesempirical conclusions of Donoho [11] and Candès et al [3]. By scaling and rounding we can easilytransform these results to obtain polynomial-time decodable random linear codes with polynomial-sized alphabets tolerating any ρ < ρ* ∠ 0.239 fraction of arbitrary errors. In the context of privacy-preserving datamining our results say thatany privacy mechanism, interactive or non-interactive, providingreasonably accurate answers to a 0.761 fraction of randomly generated weighted subset sum queries, and arbitrary answers on the remaining 0.239 fraction, is blatantly non-private.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
 |
2
|
|
| |
3
|
E.J. Candès, M. Rudelson, T. Tao, and R. Vershynin. Error correction via linear programming. In FOCS, pages 295--308. IEEE Computer Society, 2005.
|
| |
4
|
E.J. Candès and T. Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203--4215, 2005.
|
| |
5
|
E.J. Candès and T. Tao. Error correction via linear programming, 2005.
|
| |
6
|
E.J. Candès and PRandall. Highly robust error correction by convex programming. Submitted, 2006.
|
| |
7
|
|
| |
8
|
I. Dinur, C. Dwork, and K. Nissim. Privacy in public databases: A foundational approach, 2005. Manuscript.
|
| |
9
|
|
| |
10
|
D. Donoho. For most large underdetermined systems of linear equations, the minimal 11-norm near-solution approximates the sparsest near-solution. Communications on Pure and Applied Mathematics, 59(7):907--934, 2006.
|
| |
11
|
D. Donoho. For most large underdetermined systems of linear equations, the minimal l1-norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 59(6):797--829, 2006.
|
| |
12
|
D. Donoho. High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. Discrete and Computational Geometry, 35(4):617--652, 2006.
|
| |
13
|
D. Donoho and X. Huo. Uncertainty principles and ideal atomic decomposition. IEEE Transactions on Information Theory, 48:2845--2862, 2001.
|
| |
14
|
D. Donoho and I.M. Johnstone. Minimax estimation via wavelet shrinkage. Annals of Statistics, 26(3):879--921, 1998.
|
| |
15
|
D. Donoho and J. Tanner. Thresholds for the recovery of sparse solutions via l1 minimization. In Proceedings of the Conference on Information Sciences and Systems, 2006.
|
| |
16
|
D.L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289--1306, 2006.
|
| |
17
|
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In S. Halevi and T. Rabin, editors, TCC, volume 3876 of Lecture Notes in Computer Science, pages 265--284. Springer, 2006.
|
| |
18
|
C. Dwork and K. Nissim. Privacy-preserving datamining on vertically partitioned databases. In M.K. Franklin, editor, CRYPTO, volume 3152 of Lecture Notes in Computer Science, pages 528--544. Springer, 2004.
|
| |
19
|
|
| |
20
|
|
| |
21
|
J. Feldman, T. Malkin, C. Stein, R. Servedio, and M. Wainwright. LP decoding corrects a constant fraction of errors (an expanded version). In ISIT, pages 68--. IEEE, 2004.
|
| |
22
|
|
| |
23
|
L. Goldstein. l<sup>1</sup> bounds in normal approximation. Annals of Probability, 2006. To Appear.
|
| |
24
|
M. Ledoux. The Concentration of Measure Phenomenon, volume 89 of Mathematical Surveys and Monographs. American Mathematical Society, 2001.
|
| |
25
|
M. Talagrand. Concentration of measure and isoperimetric inequalities in product space. Publ. Math. I.H.E.S., 81:73--205, 1995.
|
CITED BY 8
|
|
|
|
|
Boaz Barak , Kamalika Chaudhuri , Cynthia Dwork , Satyen Kale , Frank McSherry , Kunal Talwar, Privacy, accuracy, and consistency too: a holistic solution to contingency table release, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
|
|
|
|
|
|
Dan Feldman , Amos Fiat , Haim Kaplan , Kobbi Nissim, Private coresets, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
|
|
|
|
|
|
|
|
|
Cynthia Dwork , Moni Naor , Omer Reingold , Guy N. Rothblum , Salil Vadhan, On the complexity of differentially private data release: efficient algorithms and hardness results, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
E.4