SuLQ swMATH ID: 11355 Software Authors: Blum, A., Dwork, C., McSherry, F., Nissim, K. Description: Practical privacy: the SuLQ framework. We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a database, a query consists of a pair (S, f) where S is a set of rows in the database and f is a function mapping database rows to {0, 1}. The true answer is ΣiεS f(di), and a noisy version is released as the response to the query. Results of Dinur, Dwork, and Nissim show that a strong form of privacy can be maintained using a surprisingly small amount of noise – much less than the sampling error – provided the total number of queries is sublinear in the number of database rows. We call this query and (slightly) noisy reply the SuLQ (Sub-Linear Queries) primitive. The assumption of sublinearity becomes reasonable as databases grow increasingly large.We extend this work in two ways. First, we modify the privacy analysis to real-valued functions f and arbitrary row types, as a consequence greatly improving the bounds on noise required for privacy. Second, we examine the computational power of the SuLQ primitive. We show that it is very powerful indeed, in that slightly noisy versions of the following computations can be carried out with very few invocations of the primitive: principal component analysis, k means clustering, the Perceptron Algorithm, the ID3 algorithm, and (apparently!) all algorithms that operate in the in the statistical query learning model [11]. Homepage: http://dl.acm.org/citation.cfm?id=1065184 Related Software: PrivateLR; UCI-ml; RAPPOR; ArnetMiner; gSpan; PRMLT; GotoBLAS; EMD; ARGUS; CVX Cited in: 127 Publications all top 5 Cited by 262 Authors 5 Feldman, Vitaly 5 Nissim, Kobbi 5 Ullman, Jonathan R. 5 Vadhan, Salil P. 4 Beimel, Amos 4 Bun, Mark 4 Stemmer, Uri 3 Dwork, Cynthia 3 Servedio, Rocco A. 3 Srinivasan, Srikanth 3 Vempala, Santosh S. 3 Wigderson, Avi 2 Balcan, Maria-Florina 2 Cleve, Richard 2 Ding, Jian 2 Haitner, Iftach 2 Kasiviswanathan, Shiva Prasad 2 Kawarabayashi, Ken-ichi 2 Kayal, Neeraj 2 Kreutzer, Stephan 2 Limaye, Nutan 2 Lovett, Shachar 2 Mehta, Ruta 2 Nanongkai, Danupon 2 Ostrovsky, Rafail 2 Peng, Richard 2 Roth, Aaron Leon 2 Roughgarden, Tim 2 Saha, Chandan 2 Sahai, Amit 2 Saptharishi, Ramprasad 2 Saraf, Shubhangi 2 Steurer, David 2 Talwar, Kunal 2 Vijayaraghavan, Aravindan 2 Williams, Richard Ryan 2 Woodruff, David P. 2 Yaroslavtsev, Grigory 2 Zhandry, Mark 1 Abraham, Ittai 1 Agarwal, Pankaj Kumar 1 Aggarwal, Divesh 1 Alistarh, Dan 1 Andoni, Alexandr 1 Artemenko, Sergei 1 Awasthi, Pranjal 1 Babichenko, Yakov 1 Barak, Boaz 1 Belazzougui, Djamal 1 Benkaouz, Yahya 1 Berman, Itay 1 Berman, Piotr 1 Berry, Dominic W. 1 Bhaskara, Aditya 1 Bitansky, Nir 1 Boutsidis, Christos 1 Bravyi, Sergey B. 1 Brenner, Hai 1 Buhrman, Harry 1 Bunn, Paul H. 1 Canetti, Ran 1 Censor-Hillel, Keren 1 Chan, Siu On 1 Charikar, Moses S. 1 Chechik, Shiri 1 Chekuri, Chandra S. 1 Chen, Ning 1 Cheng, Siu-Wing 1 Cheraghchi, Mahdi 1 Childs, Andrew M. 1 Choromanska, Anna 1 Choromanski, Krzysztof 1 Christiano, Paul F. 1 Chuzhoy, Julia 1 Cohen, Michael B. 1 Coja-Oghlan, Amin 1 Cole, Richard John 1 Coudron, Matthew 1 Cygan, Marek 1 Daniely, Amit 1 De, Anindya K. 1 Dekel, Ofer 1 Dekker, F. W. 1 Diakonikolas, Ilias 1 Dinur, Irit 1 Dobzinski, Shahar 1 Dodis, Yevgeniy 1 Domingo-Ferrer, Josep 1 Dvir, Zeev 1 Eisenträger, Kirsten 1 Elberfeld, Michael 1 Ene, Alina 1 Erkin, Zekeriya 1 Erradi, Mohammed 1 Forbes, Michael A. 1 Fournier, Hervé 1 Friggstad, Zachary 1 Fu, Ada Waichee 1 Galanis, Andreas 1 Garg, Jugal ...and 162 more Authors all top 5 Cited in 15 Serials 4 SIAM Journal on Computing 2 Information Sciences 2 Theoretical Computer Science 2 Algorithmica 2 Journal of Cryptology 2 Journal of Machine Learning Research (JMLR) 1 Computing 1 Journal of Computer and System Sciences 1 Mathematics of Operations Research 1 Operations Research Letters 1 Machine Learning 1 Games and Economic Behavior 1 Bernoulli 1 Statistics Surveys 1 Theory of Computing all top 5 Cited in 13 Fields 106 Computer science (68-XX) 45 Information and communication theory, circuits (94-XX) 23 Combinatorics (05-XX) 13 Operations research, mathematical programming (90-XX) 12 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 10 Numerical analysis (65-XX) 4 Statistics (62-XX) 4 Quantum theory (81-XX) 3 Linear and multilinear algebra; matrix theory (15-XX) 2 Number theory (11-XX) 2 Probability theory and stochastic processes (60-XX) 1 Mathematical logic and foundations (03-XX) 1 Statistical mechanics, structure of matter (82-XX) Citations by Year