License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.73
URN: urn:nbn:de:0030-drops-106498
URL: http://drops.dagstuhl.de/opus/volltexte/2019/10649/
Go to the corresponding LIPIcs Volume Portal


Huang, Zhiyi ; Zhu, Xue

Scalable and Jointly Differentially Private Packing

pdf-format:
LIPIcs-ICALP-2019-73.pdf (0.5 MB)


Abstract

We introduce an (epsilon, delta)-jointly differentially private algorithm for packing problems. Our algorithm not only achieves the optimal trade-off between the privacy parameter epsilon and the minimum supply requirement (up to logarithmic factors), but is also scalable in the sense that the running time is linear in the number of agents n. Previous algorithms either run in cubic time in n, or require a minimum supply per resource that is sqrt{n} times larger than the best possible.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs:2019:10649,
  author =	{Zhiyi Huang and Xue Zhu},
  title =	{{Scalable and Jointly Differentially Private Packing}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{73:1--73:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10649},
  URN =		{urn:nbn:de:0030-drops-106498},
  doi =		{10.4230/LIPIcs.ICALP.2019.73},
  annote =	{Keywords: Joint differential privacy, packing, scalable algorithms}
}

Keywords: Joint differential privacy, packing, scalable algorithms
Seminar: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 08.07.2019


DROPS-Home | Imprint | Privacy Published by LZI