English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Lipschitz extensions were recently proposed as a tool for designing nodedifferentially private algorithms. However, efficiently computable Lipschitzextensions were known only for 1-dimensional functions (that is, functions thatoutput a single real value). In this paper, we study efficiently computableLipschitz extensions for multi-dimensional (that is, vector-valued) functionson graphs. We show that, unlike for 1-dimensional functions, Lipschitzextensions of higher-dimensional functions on graphs do not always exist, evenwith a non-unit stretch. We design Lipschitz extensions with small stretch forthe sorted degree list and for the degree distribution of a graph. Crucially,our extensions are efficiently computable.  We also develop new tools for employing Lipschitz extensions in the design ofdifferentially private algorithms. Specifically, we generalize the exponentialmechanism, a widely used tool in data privacy. The exponential mechanism isgiven a collection of score functions that map datasets to real values. Itattempts to return the name of the function with nearly minimum value on thedata set. Our generalized exponential mechanism provides better accuracy whenthe sensitivity of an optimal score function is much smaller than the maximumsensitivity of score functions.  We use our Lipschitz extension and the generalized exponential mechanism todesign a node-differentially private algorithm for releasing an approximationto the degree distribution of a graph. Our algorithm is much more accurate thanalgorithms from previous work.

Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions