We introduce the notion of restricted sensitivity as an alternative to global\nand smooth sensitivity to improve accuracy in differentially private data\nanalysis. The definition of restricted sensitivity is similar to that of global\nsensitivity except that instead of quantifying over all possible datasets, we\ntake advantage of any beliefs about the dataset that a querier may have, to\nquantify over a restricted class of datasets. Specifically, given a query f and\na hypothesis H about the structure of a dataset D, we show generically how to\ntransform f into a new query f_H whose global sensitivity (over all datasets\nincluding those that do not satisfy H) matches the restricted sensitivity of\nthe query f. Moreover, if the belief of the querier is correct (i.e., D is in\nH) then f_H(D) = f(D). If the belief is incorrect, then f_H(D) may be\ninaccurate.\n We demonstrate the usefulness of this notion by considering the task of\nanswering queries regarding social-networks, which we model as a combination of\na graph and a labeling of its vertices. In particular, while our generic\nprocedure is computationally inefficient, for the specific definition of H as\ngraphs of bounded degree, we exhibit efficient ways of constructing f_H using\ndifferent projection-based techniques. We then analyze two important query\nclasses: subgraph counting queries (e.g., number of triangles) and local\nprofile queries (e.g., number of people who know a spy and a computer-scientist\nwho know each other). We demonstrate that the restricted sensitivity of such\nqueries can be significantly lower than their smooth sensitivity. Thus, using\nrestricted sensitivity we can maintain privacy whether or not D is in H, while\nproviding more accurate results in the event that H holds true.\n