Privately Releasing Conjunctions and the Statistical Query Barrier

DOI10.1137/110857714zbMath1290.68062arXiv1011.1296MaRDI QIDQ2862200

Anupam Gupta, Moritz Hardt, Jonathan R. Ullman, Aaron Roth

Publication date: 14 November 2013

Published in: SIAM Journal on Computing, Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.1296

zbMATH Keywords

agnostic learning; differential privacy; submodular functions; SQ learning

Mathematics Subject Classification ID

68Q32: Computational learning theory

68Q25: Analysis of algorithms and problem complexity

68T05: Learning and adaptive systems in artificial intelligence

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)