Fetching the paper…
Reading the bibliography…
We study the problem of answering \emph{$k$-way marginal} queries on a database $D \in (\{0,1\}^d)^n$, while preserving differential privacy.
Polynomial Threshold Functions, A C 0 AC^{0} Functions, and Spectral Norms
Jehoshua Bruck and Roman Smolensky · 1992
Earlier work this paper cites.
On the degree of polynomials that approximate symmetric boolean functions
R. Paturi · 1992
Earlier work this paper cites.
Revealing information while preserving privacy
Irit Dinur and Kobbi Nissim · 2003
Earlier work this paper cites.
Privacy-preserving datamining on vertically partitioned databases
Cynthia Dwork and Kobbi Nissim · 2004
Earlier work this paper cites.
Toward attribute efficient learning of decision lists and parities
Adam R. Klivans and Rocco A. Servedio · 2004
Earlier work this paper cites.
Practical privacy: the sulq framework
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim · 2005
Earlier work this paper cites.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith · 2006
Earlier work this paper cites.
Privacy, accuracy, and consistency too: a holistic solution to contingency table release
Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar · 2007
Earlier work this paper cites.
A learning theory approach to non-interactive database privacy
Avrim Blum, Katrina Ligett, and Aaron Roth · 2008
Earlier work this paper cites.
Robert Špalek · 2008
Earlier work this paper cites.
On the complexity of differentially private data release: efficient algorithms and hardness results
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan · 2009
Earlier work this paper cites.
The intersection of two halfspaces has high threshold degree
Alexander A. Sherstov · 2009
Earlier work this paper cites.
Boosting and differential privacy
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan · 2010
Earlier work this paper cites.
A multiplicative weights mechanism for privacy-preserving data analysis
Moritz Hardt and Guy N. Rothblum · 2010
Cited alongside, same era.
The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman · 2010
Cited alongside, same era.
Interactive privacy via the median mechanism
Aaron Roth and Tim Roughgarden · 2010
Cited alongside, same era.
Privately releasing conjunctions and the statistical query barrier
Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman · 2011
Cited alongside, same era.
On arthur merlin games in communication complexity
Hartmut Klauck · 2011
Cited alongside, same era.
The pattern matrix method
A. A. Sherstov · 2011
Cited alongside, same era.
Mirror descent based database privacy
Prateek Jain and Abhradeep Thakurta · 2012
Later among the works it cites.
The multiparty communication complexity of set disjointness
Alexander A. Sherstov · 2012
Later among the works it cites.
Strong direct product theorems for quantum communication and query complexity
Alexander A. Sherstov · 2012
Later among the works it cites.
Attribute-efficient learning and weight-degree tradeoffs for polynomial threshold functions
Rocco Servedio, Li-Yang Tan, and Justin Thaler · 2012
Later among the works it cites.
Faster algorithms for privately releasing marginals
Justin Thaler, Jonathan Ullman, and Salil P. Vadhan · 2012
Later among the works it cites.
Dual lower bounds for approximate degree and markov-bernstein inequalities
Mark Bun and Justin Thaler · 2013
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
PCPs and the hardness of generating private synthetic data
Jonathan Ullman and Salil P. Vadhan · 2011
Cited alongside, same era.
Submodular functions are noise stable
Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, and Homin K. Lee · 2012
Cited alongside, same era.
Lower bounds in differential privacy
Anindya De · 2012
Cited alongside, same era.
Iterative constructions and private data release
Anupam Gupta, Aaron Roth, and Jonathan Ullman · 2012
Cited alongside, same era.
A simple and practical algorithm for differentially private data release
Moritz Hardt, Katrina Ligett, and Frank McSherry · 2012
Cited alongside, same era.
Private data release via learning thresholds
Moritz Hardt, Guy N. Rothblum, and Rocco A. Servedio · 2012
Cited alongside, same era.
Fingerprinting codes and the true price of differential privacy
Mark Bun, Jonathan Ullman, and Salil Vadhan · 2013
Closest in time.
Efficient algorithms for privately releasing marginals via convex relaxations
Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar · 2013
Closest in time.
Learning coverage functions
Vitaly Feldman and Pravesh Kothari · 2013
Closest in time.
Low-weight halfspaces for sparse boolean vectors
Philip M. Long and Rocco A. Servedio · 2013
Closest in time.
The geometry of differential privacy: the sparse and approximate cases
Aleksandar Nikolov, Kunal Talwar, and Li Zhang · 2013
Closest in time.
Answering n 2+o(1) {}^{\mbox{2+o(1)}} counting queries with differential privacy is hard
Jonathan Ullman · 2013
Closest in time.