{"id":"arxiv/2611.06670","url":"https://arxiv.org/abs/2611.06670","tags":["cs.DS","math.ST"],"score":0,"title":"Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error","domain":"cs.DS","source":"arxiv","authors":["Marek Eliáš","Gautam Kamath","Janardhan Kulkarni","George Z. Li","Jingcheng Liu","Sepideh Mahabadi","Pan Peng","Jakub Tarnawski","Hangyu Xu","Zongrui Zou"],"reviews":0,"subject":"cs.DS","summary":"We give a polynomial-time $(\\varepsilon, δ)$-edge-differentially private algorithm that releases a synthetic graph approximately preserving all cut values of a nonnegative weighted input graph $G$. Our algorithm outputs a nonnegative weighted graph $H$ such that, with probability at least $1-β$, simultaneously for all $S\\subseteq V$, \\[ \\left|w_G(S,V\\setminus S)-w_H(S,V\\setminus S)\\right| \\leq γw_G(S,V\\setminus S) + O\\left(\\frac{n}{γ\\varepsilon} \\log^7 \\frac{n}{δβγ\\varepsilon}\\right). \\] For fixed $γ, \\varepsilon$ and $δ= β= n^{-10}$, the additive error is $n \\operatorname{polylog} n$,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}