%=======================02-713 LaTeX template, following the 15-210 template==================
%
% You don't need to use LaTeX or this template, but you must turn your homework in as
% a typeset PDF somehow.
%
% How to use:
% 1. Update your information in section "A" below
% 2. Write your answers in section "B" below. Precede answers for all
% parts of a question with the command "\question{n}{desc}" where n is
% the question number and "desc" is a short, one-line description of
% the problem. There is no need to restate the problem.
% 3. If a question has multiple parts, precede the answer to part x with the
% command "\part{x}".
% 4. If a problem asks you to design an algorithm, use the commands
% \algorithm, \correctness, \runtime to precede your discussion of the
% description of the algorithm, its correctness, and its running time, respectively.
% 5. You can include graphics by using the command \includegraphics{FILENAME}
%
\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{graphicx}
\usepackage[margin=1in]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 1pt}
\setlength{\headheight}{13.6pt}
\newcommand\question[2]{\vspace{.25in}\hrule\textbf{#1: #2}\vspace{.5em}\hrule\vspace{.10in}}
\renewcommand\part[1]{\vspace{.10in}\textbf{(#1)}}
\newcommand\algorithm{\vspace{.10in}\textbf{Algorithm: }}
\newcommand\correctness{\vspace{.10in}\textbf{Correctness: }}
\newcommand\runtime{\vspace{.10in}\textbf{Running time: }}
\pagestyle{fancyplain}
\lhead{\textbf{\NAME\ }}
\chead{\textbf{Homework 3}} % for course ``Information theory in theoretical computer science"}}
\rhead{COMS6998, \today}
\newcommand\eps{\epsilon}
\newcommand\x{\bf x \rm}
\newcommand\y{\bf y \rm}
\newcommand\supp{Supp}
\newcommand\E{\mathbb{E}}
\newcommand\cE{\mathcal{E}}
\newcommand\solution{\bf Solution \rm}
% KL DIVERGENCE :
\providecommand{\Div}[2]{\mathsf{D}\left(\begin{array}{c} #1 \\ \hline \hline #2\end{array} \right)}
\renewcommand{\div}[2]{\mathsf{D}\left( #1 || #2\right)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}\raggedright
%Section A==============Change the values below to match your information==================
\newcommand\NAME{Instructor: Omri Weinstein \\ TA: Zhenrui Liao} % your name
\newcommand\HWNUM{1} % the homework number
%Section B==============Put your answers to the questions below here=======================
% no need to restate the problem --- the graders know which problem is which,
% but replacing "The First Problem" with a short phrase will help you remember
% which problem this is when you read over your homeworks to study.
\question{1}{Problem 1 (Randomized and Distributional Communication Complexity) 25 pts}
Let $f: \{0,1\}^n \times \{0,1\}^n \mapsto \{0,1\}$ be a $2$-party Boolean function.
\part{1} Show that $f$ admits a $2$-bit randomized (public-coin) communication protocol that succeeds
with probability $\geq 1/2 + 2^{-2n}$. %, i.e., $R_{1/2 + 2^{-2n}}(f) \leq 2$.
\part{2} Show that for any prior distribution $\mu$, there is a $2$-bit protocol for $f$ with success probability
$\geq 1/2+ Disc_{\mu}(f)$, where $Disc_{\mu}(f)$ is the discrepancy of $f$ w.r.t $\mu$. %, i.e., $D^{1/2 - Disc_{\mu}}_\mu (f) \leq 2$.
\part{3} Show that $R^{priv}_{1/3}(f) \geq \lg D(f)$, where $D(f)$ is the deterministic communication complexity
of $f$ and $R^{priv}_{1/3}(f)$ is the private-coin randomized communication complexity of $f$ with error $1/3$.
(For simplicity, you may assume that the probabilities of transmitting $0/1$ in any execution of a randomized
protocol for $f$ are rational numbers).
%What can Alice and Bob do (deterministically) had they knew
%$\Pr(\pi_i = 1 | \pi_{