高级算法 (Fall 2022)/Problem Set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Roundgod (talk | contribs)
added hw2 page
 
Roundgod (talk | contribs)
 
(12 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Problem 1 ==
== Problem 1 ==
Suppose we want to estimate the value of  <math>Z</math>. Let  <math>\mathcal{A}</math> be an algorithm that outputs <math>\widehat{Z}</math> satisfying
<math>\Pr[ (1-\epsilon)Z \leq \widehat{Z} \leq (1+\epsilon )Z] \geq \frac{3}{4} .</math>
We run  <math>\mathcal{A}</math> independently for <math>s</math> times, and obtain the outputs <math>\widehat{Z}_1,\widehat{Z}_2,\ldots,\widehat{Z}_s</math>.
Let <math>X</math> be the '''median''' (中位数) of <math>\widehat{Z}_1,\widehat{Z}_2,\ldots,\widehat{Z}_s</math>. Find the number <math>s</math> such that <math>\Pr[ (1-\epsilon)Z \leq X \leq (1+\epsilon )Z] \geq 1 - \delta .</math>
Express <math>s</math> as a function of <math>\delta</math>. Make <math>s</math> as small as possible.
'''Remark''': in this problem, we boost the probability of success from <math>\frac{3}{4}</math> to <math>1-\delta</math>. This method is called the median trick.
'''Hint''': Chernoff bound.
== Problem 2 ==
Let <math>X</math> be a random variable with expectation <math>0</math> such that moment generating function <math>\mathbf{E}[\exp(t|X|)]</math> is finite for some <math> t > 0 </math>. We can use the following two kinds of tail inequalities for <math> X </math>.
'''''Chernoff Bound'''''
:<math>
\begin{align}
\mathbf{Pr}[|X| \geq \delta] \leq \min_{t \geq 0} \frac{\mathbf{E}[e^{t|X|}]}{e^{t\delta}}
\end{align}
</math>
'''''<math>k</math>th-Moment Bound'''''
:<math>
\begin{align}
\mathbf{Pr}[|X| \geq \delta] \leq \frac{\mathbf{E}[|X|^k]}{\delta^k}
\end{align}
</math>
* Show that for each <math>\delta</math>, there exists a choice of <math>k</math> such that the <math>k</math>th-moment bound is stronger than the Chernoff bound.
 
  '''''Hint''''': Consider the Taylor expansion of the moment generating function and apply the probabilistic method.
* Why would we still prefer the Chernoff bound to the (seemingly) stronger <math>k</math>-th moment bound?
== Problem 3 ==
Let <math> \Omega </math> be a finite set of size <math> m </math>. Let  <math>\mathcal{A}=\{A_1,A_2,\dots,A_n\}</math> be a family of <math> n </math> subsets of <math>\Omega </math>. For any "coloring" <math>\chi:\Omega\rightarrow \{-1,+1\} </math> that maps each element of <math>\Omega </math> to  <math> -1 </math> or <math> +1 </math>, and any subset <math>A\subseteq \Omega </math>, we define
<math>
\begin{align}
\chi(A)\triangleq \sum\limits_{a\in A}\chi(a).
\end{align}
</math>
Define the '''discrepancy''' of the family of subsets <math>\mathcal{A}</math> with respect to the "coloring"<math>\chi</math> by
<math>
\begin{align}
\quad\textsf{disc}(\mathcal{A},\chi)\triangleq \max\limits_{A\in \mathcal{A}}|\chi(A)|,
\end{align}
</math>
and the '''discrepancy''' of <math> \mathcal{A} </math> by
<math>
\begin{align}
\quad\textsf{disc}(\mathcal{A})\triangleq \min\limits_{\chi:\Omega\rightarrow\{-1,+1\}} \textsf{disc}(\mathcal{A},\chi).
\end{align}
</math>
* Show that
<math>
\quad\textsf{disc}(\mathcal{A})\leq \sqrt{2m\ln{(2n)}}.
</math>
'''''Hint''''': Apply the probabilistic method.
* Suppose <math> m </math> is even. Show further that
<math>
\quad\textsf{disc}(\mathcal{A})\leq \sqrt{m\ln{(2n)}}.
</math>
'''''Hint''''': Set <math>\chi(i+\frac{m}{2})=-\chi(i)</math> for <math> 1\leq i\leq \frac{m}{2}.</math>
== Problem 4 ==
Given an undirected graph <math>G(V, E)</math> with maximum degree <math>\Delta</math>, where the vertex set <math>V</math> is partitioned into <math>r</math> disjoint subsets, i.e., <math>V = S_1 \cup S_2 \cup \cdots \cup S_r</math> with <math>S_i \cap S_j = \varnothing</math> for all <math>i \neq j</math>. We call a vertex set <math>T</math> is a transversal of the partition <math>\{S_1, S_2, \cdots, S_r\}</math>, if <math>|T \cap S_i| = 1</math> for all <math>1 \leq i \leq r</math>. Assume that <math>|S_i| \geq 2e\Delta</math> for all <math>1 \leq i \leq r </math>.
1. Prove that there must be an independent transversal (a transversal which is also an independent set) of <math>\{S_1, S_2, \cdots, S_r\}</math>.
'''Hint''': Lovász Local Lemma.
2. Design a randomized algorithm that finds an independent transversal of <math>\{S_1, S_2, \cdots, S_r\}</math> in expected polynomial time.
== Problem 5 ==
Let <math>D=(V,E)</math> be a simple directed graph with '''minimum outdegree''' <math>\delta</math> and '''maximum indegree''' <math>\Delta</math>. Prove:
For any positive integer <math> k</math>, if <math>\mathrm{e}(\Delta \delta+1)(1-\frac{1}{k})^{\delta}<1</math>, then  <math>D</math> contains a (directed,simple) cycle of length <math>0\pmod k.</math>
'''Hint''': Let <math>f:V\rightarrow \{0,1,\dots,k-1\}</math> be a random coloring of <math> V </math> obtained by choosing uniformly and independently at random for each <math> v\in V</math>. Try to use Lovász Local Lemma to show something interesting!

Latest revision as of 14:36, 31 October 2022

Problem 1

Suppose we want to estimate the value of [math]\displaystyle{ Z }[/math]. Let [math]\displaystyle{ \mathcal{A} }[/math] be an algorithm that outputs [math]\displaystyle{ \widehat{Z} }[/math] satisfying [math]\displaystyle{ \Pr[ (1-\epsilon)Z \leq \widehat{Z} \leq (1+\epsilon )Z] \geq \frac{3}{4} . }[/math]

We run [math]\displaystyle{ \mathcal{A} }[/math] independently for [math]\displaystyle{ s }[/math] times, and obtain the outputs [math]\displaystyle{ \widehat{Z}_1,\widehat{Z}_2,\ldots,\widehat{Z}_s }[/math].

Let [math]\displaystyle{ X }[/math] be the median (中位数) of [math]\displaystyle{ \widehat{Z}_1,\widehat{Z}_2,\ldots,\widehat{Z}_s }[/math]. Find the number [math]\displaystyle{ s }[/math] such that [math]\displaystyle{ \Pr[ (1-\epsilon)Z \leq X \leq (1+\epsilon )Z] \geq 1 - \delta . }[/math]

Express [math]\displaystyle{ s }[/math] as a function of [math]\displaystyle{ \delta }[/math]. Make [math]\displaystyle{ s }[/math] as small as possible.

Remark: in this problem, we boost the probability of success from [math]\displaystyle{ \frac{3}{4} }[/math] to [math]\displaystyle{ 1-\delta }[/math]. This method is called the median trick.

Hint: Chernoff bound.

Problem 2

Let [math]\displaystyle{ X }[/math] be a random variable with expectation [math]\displaystyle{ 0 }[/math] such that moment generating function [math]\displaystyle{ \mathbf{E}[\exp(t|X|)] }[/math] is finite for some [math]\displaystyle{ t \gt 0 }[/math]. We can use the following two kinds of tail inequalities for [math]\displaystyle{ X }[/math].

Chernoff Bound

[math]\displaystyle{ \begin{align} \mathbf{Pr}[|X| \geq \delta] \leq \min_{t \geq 0} \frac{\mathbf{E}[e^{t|X|}]}{e^{t\delta}} \end{align} }[/math]

[math]\displaystyle{ k }[/math]th-Moment Bound

[math]\displaystyle{ \begin{align} \mathbf{Pr}[|X| \geq \delta] \leq \frac{\mathbf{E}[|X|^k]}{\delta^k} \end{align} }[/math]
  • Show that for each [math]\displaystyle{ \delta }[/math], there exists a choice of [math]\displaystyle{ k }[/math] such that the [math]\displaystyle{ k }[/math]th-moment bound is stronger than the Chernoff bound.
 Hint: Consider the Taylor expansion of the moment generating function and apply the probabilistic method.
  • Why would we still prefer the Chernoff bound to the (seemingly) stronger [math]\displaystyle{ k }[/math]-th moment bound?

Problem 3

Let [math]\displaystyle{ \Omega }[/math] be a finite set of size [math]\displaystyle{ m }[/math]. Let [math]\displaystyle{ \mathcal{A}=\{A_1,A_2,\dots,A_n\} }[/math] be a family of [math]\displaystyle{ n }[/math] subsets of [math]\displaystyle{ \Omega }[/math]. For any "coloring" [math]\displaystyle{ \chi:\Omega\rightarrow \{-1,+1\} }[/math] that maps each element of [math]\displaystyle{ \Omega }[/math] to [math]\displaystyle{ -1 }[/math] or [math]\displaystyle{ +1 }[/math], and any subset [math]\displaystyle{ A\subseteq \Omega }[/math], we define [math]\displaystyle{ \begin{align} \chi(A)\triangleq \sum\limits_{a\in A}\chi(a). \end{align} }[/math]

Define the discrepancy of the family of subsets [math]\displaystyle{ \mathcal{A} }[/math] with respect to the "coloring"[math]\displaystyle{ \chi }[/math] by

[math]\displaystyle{ \begin{align} \quad\textsf{disc}(\mathcal{A},\chi)\triangleq \max\limits_{A\in \mathcal{A}}|\chi(A)|, \end{align} }[/math]

and the discrepancy of [math]\displaystyle{ \mathcal{A} }[/math] by

[math]\displaystyle{ \begin{align} \quad\textsf{disc}(\mathcal{A})\triangleq \min\limits_{\chi:\Omega\rightarrow\{-1,+1\}} \textsf{disc}(\mathcal{A},\chi). \end{align} }[/math]

  • Show that

[math]\displaystyle{ \quad\textsf{disc}(\mathcal{A})\leq \sqrt{2m\ln{(2n)}}. }[/math]

Hint: Apply the probabilistic method.

  • Suppose [math]\displaystyle{ m }[/math] is even. Show further that

[math]\displaystyle{ \quad\textsf{disc}(\mathcal{A})\leq \sqrt{m\ln{(2n)}}. }[/math]

Hint: Set [math]\displaystyle{ \chi(i+\frac{m}{2})=-\chi(i) }[/math] for [math]\displaystyle{ 1\leq i\leq \frac{m}{2}. }[/math]

Problem 4

Given an undirected graph [math]\displaystyle{ G(V, E) }[/math] with maximum degree [math]\displaystyle{ \Delta }[/math], where the vertex set [math]\displaystyle{ V }[/math] is partitioned into [math]\displaystyle{ r }[/math] disjoint subsets, i.e., [math]\displaystyle{ V = S_1 \cup S_2 \cup \cdots \cup S_r }[/math] with [math]\displaystyle{ S_i \cap S_j = \varnothing }[/math] for all [math]\displaystyle{ i \neq j }[/math]. We call a vertex set [math]\displaystyle{ T }[/math] is a transversal of the partition [math]\displaystyle{ \{S_1, S_2, \cdots, S_r\} }[/math], if [math]\displaystyle{ |T \cap S_i| = 1 }[/math] for all [math]\displaystyle{ 1 \leq i \leq r }[/math]. Assume that [math]\displaystyle{ |S_i| \geq 2e\Delta }[/math] for all [math]\displaystyle{ 1 \leq i \leq r }[/math].

1. Prove that there must be an independent transversal (a transversal which is also an independent set) of [math]\displaystyle{ \{S_1, S_2, \cdots, S_r\} }[/math].

Hint: Lovász Local Lemma.

2. Design a randomized algorithm that finds an independent transversal of [math]\displaystyle{ \{S_1, S_2, \cdots, S_r\} }[/math] in expected polynomial time.

Problem 5

Let [math]\displaystyle{ D=(V,E) }[/math] be a simple directed graph with minimum outdegree [math]\displaystyle{ \delta }[/math] and maximum indegree [math]\displaystyle{ \Delta }[/math]. Prove:

For any positive integer [math]\displaystyle{ k }[/math], if [math]\displaystyle{ \mathrm{e}(\Delta \delta+1)(1-\frac{1}{k})^{\delta}\lt 1 }[/math], then [math]\displaystyle{ D }[/math] contains a (directed,simple) cycle of length [math]\displaystyle{ 0\pmod k. }[/math]


Hint: Let [math]\displaystyle{ f:V\rightarrow \{0,1,\dots,k-1\} }[/math] be a random coloring of [math]\displaystyle{ V }[/math] obtained by choosing uniformly and independently at random for each [math]\displaystyle{ v\in V }[/math]. Try to use Lovász Local Lemma to show something interesting!