Jingcheng Liu

Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers

A primitive with a sharper error dependence on $n$ and $d$ for the downstream cut approximation is developed and combined with a new edge-sensitive terminal cut oracle with additive error yields the final worst-case polynomial-time private cut-release error.