Near-Universally-Optimal Differentially Private Minimum Spanning Trees

arXiv:2404.15035v1 Announce Type: new
Abstract: Devising mechanisms with good beyond-worst-case input-dependent performance has been an important focus of differential privacy, with techniques such as smooth sensitivity, propose-test-release, or inverse sensitivity mechanism being developed to achieve this goal. This makes it very natural to use the notion of universal optimality in differential privacy. Universal optimality is a strong instance-specific optimality guarantee for problems on weighted graphs, which roughly states that for any fixed underlying (unweighted) graph, the algorithm is optimal in …

arxiv beyond case cs.cr cs.ds differential privacy focus goal good important input mechanism natural near notion performance privacy private release spanning techniques test trees