\documentclass[11pt]{article}
\usepackage{amsmath, alltt, amssymb, xspace, times, epsfig}
\usepackage{hyperref}
\urlstyle{same}

\setlength{\evensidemargin}{0in} \setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in} \setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in} \setlength{\headheight}{0in}

\renewcommand{\Pr}{\ensuremath{\mathbf{Pr}}\xspace}

\newcommand{\tuple}[1]{\ensuremath{\langle #1 \rangle}\xspace}

\newcommand{\PT}{\ensuremath{\mathsf{PT}}\xspace}
\newcommand{\CT}{\ensuremath{\mathsf{CT}}\xspace}
\newcommand{\Key}{\ensuremath{\mathsf{Key}}\xspace}

\newcommand{\CC}{\ensuremath{\mathcal{C}}\xspace}
\newcommand{\KK}{\ensuremath{\mathcal{K}}\xspace}
\newcommand{\MM}{\ensuremath{\mathcal{M}}\xspace}

\newcommand{\E}{\ensuremath{\mathbb{E}}\xspace}
\newcommand{\D}{\ensuremath{\mathbb{D}}\xspace}
\newcommand{\K}{\ensuremath{\mathbb{K}}\xspace}

\newcommand{\Gen}{\ensuremath{\mathsf{Gen}}\xspace}
\newcommand{\Enc}{\ensuremath{\mathsf{Enc}}\xspace}
\newcommand{\Dec}{\ensuremath{\mathsf{Dec}}\xspace}



\begin{document}

\thispagestyle{empty}

\noindent \textbf{CS590 DSP: Data Security and Privacy\hspace*{\fill}Spring 2022}
\begin{center}
{\LARGE Homework \#5}
\end{center}

\paragraph{Due date \& time:} 11:59pm on April 19, 2022.
% Hand in at the beginning of class (preferred), or email to the TA
% (li2490@purdue.edu) by the due time.
\underline{Please hand in your homework on Brightspace.}

\vspace*{-0.1in}\paragraph{Late Policy:} You have three extra days in total for all
your homeworks and projects.  Any portion of a day used counts as one day; that is,
you have to use integer number of late days each time. If
you exhaust your three late days, any late homework won't be graded.


\vspace*{-0.1in}\paragraph{Additional Instructions:} (1) The submitted homework must be typed. Using Latex is recommended, but not required.
\\


\begin{description}



 \item[Problem 1 (25 pts) ]
Read the paper ``Understanding Hierarchical Methods for Differentially Private Histograms'' by  Qardaji et al., and answer the following questions. \\
\url{http://www.vldb.org/pvldb/vol6/p1954-qardaji.pdf}
\begin{itemize}
    \item 
    Explain why using a hierarchy helps reduce the error of range queries in one-dimensional dataset. 
    
    \item 
    Explain the key factors where one can optimize the accuracy of hierarchical methods, and their impacts. 

    \item 
    The analysis in the paper assumes that we want to optimize absolute (squared) error.  What if we want to optimize for relative error, that is, absolute error divided by true answer, (or some constant $\sigma$ when the true answer is below $\sigma$)?  What kind of hierarchical method do you think would be the nest? 


%    \item 
%    The analysis of multi-dimensional case (Section 5) assumes that we use a flat partitioning in higher dimensional space.  The 2D range-tree data structure is actually different
%    \url{https://www.geeksforgeeks.org/two-dimensional-segment-tree-sub-matrix-sum/}
    
\end{itemize}


 \item[Problem 2 (25 pts) ]
Read the paper ``PriView: practical differentially private release of marginal contingency tables. '' by  Qardaji et al., and answer the following questions. \\
\url{https://dl.acm.org/doi/10.1145/2588555.2588575}
\begin{itemize}
    \item
    Give a summary of how the PriView method work. 
    
    \item
    Explain the different methods for reconstructing a $k$-way marginal, once a number of views have been obtained and made consistent.  How well do they compare with each other?
    
    \item 
    How to extend the method to deal with datasets that have attributes that not binary, especially numerical attributes?

    \item 
    On what kinds of datasets and queries would the method in PriView result in high errors?
    
\end{itemize}

 \item[Problem 3 (50 pts) ]  Study how Census Bureau applies differential privacy.  Write a report analyzing how Census Bureau currently applies Differential Privacy, and in what ways can it be improved.  The report should be at least 3 pages in single space and 11pt font, i.e., in the formatting of this assignment document. 
One starting point is  \\
\url{https://www.ncsl.org/research/redistricting/differential-privacy-for-census-data-explained.aspx}

\end{description}

\end{document}


