差别隐私
图形
算法
组合数学
计算机科学
离散数学
数学
作者
Marek Eliáš,Michael Kapralov,Janardhan Kulkarni,Yin Tat Lee
出处
期刊:Society for Industrial and Applied Mathematics eBooks
[Society for Industrial and Applied Mathematics]
日期:2020-01-01
卷期号:: 560-578
被引量:11
标识
DOI:10.1137/1.9781611975994.34
摘要
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)Differentially Private Release of Synthetic GraphsMarek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat LeeMarek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Leepp.560 - 578Chapter DOI:https://doi.org/10.1137/1.9781611975994.34PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We propose a (ϵ, δ)-differentially private mechanism that, given an input graph G with n vertices and m edges, in polynomial time generates a synthetic graph G’ approximating all cuts of the input graph up to an additive error of . This is the first construction of differentially private cut approximator that allows additive error o(m) for all m > n logC n. The best known previous results gave additive O(n3/2) error and hence only retained information about the cut structure on very dense graphs. Thus, we are making a notable progress on a promiment problem in differential privacy. We also present lower bounds showing that our utility/privacy trade-off is essentially the best possible if one seeks to get purely additive cut approximations. Previous chapter Next chapter RelatedDetails Published:2020eISBN:978-1-61197-599-4 https://doi.org/10.1137/1.9781611975994Book Series Name:ProceedingsBook Code:PRDA20Book Pages:xxii + 3011
科研通智能强力驱动
Strongly Powered by AbleSci AI