File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.4230/LIPIcs.ICALP.2019.73
- Scopus: eid_2-s2.0-85069170843
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Scalable and Jointly Differentially Private Packing
Title | Scalable and Jointly Differentially Private Packing |
---|---|
Authors | |
Keywords | Joint differential privacy Packing Scalable algorithms |
Issue Date | 2019 |
Publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. |
Citation | 46th International Colloquium on Automata, Languages, and Programming (ICALP), Patras, Greece, 8-12 July 2019, article 73, p. 73:1-73:12 How to Cite? |
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. |
Description | Track: A - Session A.2.1 |
Persistent Identifier | http://hdl.handle.net/10722/273019 |
ISBN | |
Series/Report no. | Leibniz International Proceedings in Informatics (LIPIcs) ; v. 132 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Zhu, X | - |
dc.date.accessioned | 2019-08-06T09:21:00Z | - |
dc.date.available | 2019-08-06T09:21:00Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | 46th International Colloquium on Automata, Languages, and Programming (ICALP), Patras, Greece, 8-12 July 2019, article 73, p. 73:1-73:12 | - |
dc.identifier.isbn | 9783959771092 | - |
dc.identifier.uri | http://hdl.handle.net/10722/273019 | - |
dc.description | Track: A - Session A.2.1 | - |
dc.description.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. | - |
dc.language | eng | - |
dc.publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. | - |
dc.relation.ispartof | 46th International Colloquium on Automata, Languages, and Programming (ICALP) | - |
dc.relation.ispartofseries | Leibniz International Proceedings in Informatics (LIPIcs) ; v. 132 | - |
dc.subject | Joint differential privacy | - |
dc.subject | Packing | - |
dc.subject | Scalable algorithms | - |
dc.title | Scalable and Jointly Differentially Private Packing | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Huang, Z: zhiyi@cs.hku.hk | - |
dc.identifier.authority | Huang, Z=rp01804 | - |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.4230/LIPIcs.ICALP.2019.73 | - |
dc.identifier.scopus | eid_2-s2.0-85069170843 | - |
dc.identifier.hkuros | 299946 | - |
dc.identifier.volume | 132 | - |
dc.identifier.spage | 73:1 | - |
dc.identifier.epage | 73:12 | - |
dc.publisher.place | Dagstuhl, Germany | - |