Facilitating use of sensitive data for research or commercial purposes, in a manner that preserves the privacy of participating entities, is an active area of study. Differential privacy is a popular, relatively recent, framework that formalizes data privacy. In this dissertation, I examine the often conflicting goals of privacy and utility within the framework of differential privacy. The contributions of this dissertation fall into two main categories:

1) We propose differentially private algorithms for several tasks that could potentially involve sensitive data, such as synthetic graph modeling, human mobility modeling using cellular phone data, regression, and computing statistics on online data.

We study the tradeoff between privacy and utility for these analyses--- theoretically in some cases, and experimentally in others. We show that for each of these tasks, both privacy and utility can be successfully achieved by considering a meaningful tradeoff between the two.

2) We also examine connections between information theory and differential privacy, demonstrating how differential privacy arises out of a tradeoff between information leakage and utility. We establish a connection between a well studied problem in information theory--- the rate-distortion problem --- and differential privacy and show that probability distributions that achieve the rate-distortion bound are also differentially private.