# 高级算法 (Fall 2021)/Problem Set 1

• 每道题目的解答都要有完整的解题过程。中英文不限。

## Problem 1

Recall that in class we show by the probabilistic method how to deduce a $\frac{n(n-1)}{2}$ upper bound on the number of distinct min-cuts in any multigraph $G$ with $n$ vertices from the $\frac{2}{n(n-1)}$ lower bound for success probability of Karger's min-cut algorithm.

Also recall that the $FastCut$ algorithm taught in class guarantees to return a min-cut with probability at least $\Omega(1/\log n)$. Does this imply a much tighter $O(\log n)$ upper bound on the number of distinct min-cuts in any multigraph $G$ with $n$ vertices? Prove your improved upper bound if your answer is "yes", and give a satisfactory explanation if your answer is "no".

## Problem 2

Consider the function $f:\mathbb{R}^n\to\mathbb{R}$ defined as

$f(\vec x)=f(x_1,x_2,\dots,x_n)=\prod_{i=1}^{n}(a_ix_i-b_i)$,

where $\{a_i\}_{1\le i\le n}$ and $\{b_i\}_{1\le i\le n}$ are unknown coefficients satisfy that $a_i, b_i\in \mathbb{Z}$ and $0\le a_i, b_i \le n$ for all $1\le i\le n$.

Let $p\gt n$ be the smallest prime strictly greater than $n$. The function $g:\mathbb{Z}_p^n\to\mathbb{Z}_p$ is defined as

$g(\vec x)=g(x_1,x_2,\dots,x_n)=\prod_{i=1}^{n}(a_ix_i-b_i)$,

where $+$ and $\cdot$ are defined over the finite field $\mathbb{Z}_p$.

By the properties of finite field, for any value $\vec r\in\mathbb{Z}_p^n$, it holds that $g(\vec r)=f(\vec r)\bmod p$.

Since the coefficients $\{a_i\}_{1\le i\le n}$ and $\{b_i\}_{1\le i\le n}$ are unknown, you can't calculate $f(\vec x)$ directly. However, there exists an oracle $O$, each time $O$ gets an input $\vec x$, it immediately outputs the value of $g(\vec x)$.

1. Prove that $f\not\equiv 0 \Rightarrow g\not\equiv 0$.

2. Use the oracle $O$ to design an algorithm to determine whether $f\equiv 0$, with error probability at most $\epsilon$, where $\epsilon\in (0,1)$ is a constant.

## Problem 3

Let $X_1,X_2,\ldots,X_n$ be $n$ random variables, where each $X_i \in \{0, 1\}$ follows the distribution $\mu_i$. For each $1\leq i \leq n$, let $\rho_i = \mathbb{E}[X_i]$ and assume $\rho_i \geq \frac{1}{2}$. Consider the problem of estimating the value of

$Z = \prod_{i = 1}^n \rho_i$.

For each $1\leq i \leq n$, the algorithm draws $s$ random samples $X_i^{(1)},X_i^{(2)},\ldots,X_i^{(s)}$ independently from the distribution $\mu_i$, and computes

$\widehat{\rho}_{i}=\frac{1}{s}\sum_{j=1}^s X_i^{(j)}$.

Finally, the algorithm outputs the product of all $\widehat{Z}_{i}$:

$\widehat{Z}=\prod_{i= 1}^n\widehat{\rho}_i$.

Express $s$ as a function of $n,\varepsilon,\delta$ so that the output $\widehat{Z}$ satisfies

$\Pr\left[(1 - \varepsilon) Z \leq \widehat{Z} \leq (1 + \varepsilon)Z\right] \geq 1- \delta$.

Try to make $s$ as small as possible.

## Problem 4

Suppose there is a coin $C$. During each query, it outputs HEAD with probability $p$ and TAIL with probability $1-p$, where $p \in (0, 1)$ is a real number.

• Let $q \in (0, 1)$ be another real number. Design an algorithm that outputs HEAD with probability $q$ and TAIL with probability $1-q$. There is no other random sources for your algorithm except the coin $C$. Make sure that your algorithm halts with probability $1$.
• What is the expected number of queries for the coin $C$ that your algorithm use before it halts?