We initiate a systematic study of algorithms that are both differentially private and run in sublinear time for several problems in which the goal is to estimate natural graph parameters. Our main result is a differentially-private $(1+\rho)$-approximation algorithm for the problem of computing the average degree of a graph, for every $\rho>0$. The running time of the algorithm is roughly the same as its non-private version proposed by Goldreich and Ron (Sublinear Algorithms, 2005). We also obtain the first differentially-private sublinear-time approximation algorithms for the maximum matching size and the minimum vertex cover size of a graph. An overarching technique we employ is the notion of coupled global sensitivity of randomized algorithms. Related variants of this notion of sensitivity have been used in the literature in ad-hoc ways. Here we formalize the notion and develop it as a unifying framework for privacy analysis of randomized approximation algorithms.

翻译：我们开始系统研究两种不同的私人算法,这些算法的运行时间与Goldreich和Ron提出的非私人版本大致相同(Sublinear Algorithms,2005年)。我们还获得了第一个用于估计自然图参数的差别-私人次线性近似算法,用于估计一个图的最大匹配大小和最小顶层大小。我们使用的一种总体技术是随机算法的全球敏感性概念。文献中以临时方式使用了这种敏感概念的相关变体。我们在这里将这一概念正式化并发展为随机近似算法的隐私分析的统一框架。