CMU-CS-13-120Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-13-120
Or Sheffet August 2013 Ph.D. Thesis
Keywords:
Non Worst-Case Analysis, Differential Privacy, Clustering, Algorithms
This thesis can be viewed as a collection of work in differential privacy
and in clustering. In its first part we discuss work aimed at preserving
differential privacy in a social network, with respect to either the
presence/absence of a single edge [41], or with respect to changing all edges
adjacent to one node [42]. In its second part we discuss multiple clustering
problems, focusing on the
Alternatively, this thesis can be viewed as an investigation of specific
nonworst case analysis paradigms. The common theme among of all results
composing this thesis is that they all introduce algorithms whose guarantees
are meaningful only for a subset of inputs – for inputs that satisfy
certain nice properties, or assumptions. These assumptions can be roughly
divided into two types, which we refer to as explicit or implicit. Explicit
assumptions give a very specific and quantifiable characterization of the
input (e.g. clustering instances with the distance between any pair of
cluster centers larger than a specific bound). On the other hand, implicit
assumptions are harder to characterize. Implicit assumptions pose a certain
property that the input should satisfy, due to some compelling
"real-life" reasoning (e.g. justifying a particular
value of 178 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |