随机算法 (Spring 2013)/Problem Set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
Line 16: Line 16:


Give an analysis to lower bound the probability that a single iteration of Karger's Random Contraction algorithm returns an <math>\alpha</math>-min-cut in a graph <math>G(V,E)</math> of <math>n</math> vertices and <math>m</math> edges.
Give an analysis to lower bound the probability that a single iteration of Karger's Random Contraction algorithm returns an <math>\alpha</math>-min-cut in a graph <math>G(V,E)</math> of <math>n</math> vertices and <math>m</math> edges.
== Problem 4 ==
{{Theorem|Freivalds' Theorem|
:Let <math>A</math> be an <math>n\times n</math> matrix such that <math>A\neq\boldsymbol{0}</math>. For a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[Ar = \boldsymbol{0}]\le \frac{1}{2}</math>.
}}
{{Theorem|Schwartz-Zippel Theorem|
: Let <math>f\in\mathbb{F}[x_1,x_2,\ldots,x_n]</math> be a multivariate polynomial of degree <math>d</math> over a field <math>\mathbb{F}</math> such that <math>f\not\equiv 0</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,r_2\ldots,r_n</math> be chosen uniformly and independently at random from <math>S</math>. Then
::<math>\Pr[f(r_1,r_2,\ldots,r_n)=0]\le\frac{d}{|S|}.</math>
}}
Prove that Schwartz-Zippel Theorem implies Freivalds Theorem.

Revision as of 13:28, 11 March 2013

Problem 1

  • Suppose that you are given a coin for which the probability of HEADS, say [math]\displaystyle{ p }[/math], is unknown. How can you use this coin to generate unbiased (i.e., [math]\displaystyle{ \Pr[\mathrm{HEADS}]=\Pr[\mathrm{TAILS}]=1/2 }[/math]) coin-flips? Give a scheme for which the expected number of flips of the biased coin for extracting one unbiased coin-flip is no more than [math]\displaystyle{ \frac{1}{p(1-p)} }[/math].

Problem 2

We start with [math]\displaystyle{ n }[/math] people, each with 2 hands. None of these hands hold each other.

At each round, we uniformly pick 2 free hands and let them hold together.

  • After how many rounds, there are no free hands left?
  • What is the expected number of cycles made by people holding hands with each other (one person with left hand holding right hand is also counted as a cycle), when there are no free hands left?

(Hint: Consider how to count the number of cycles using indicator random variables.)

Problem 3

For any [math]\displaystyle{ \alpha\ge 1 }[/math], a cut [math]\displaystyle{ C }[/math] in an undirected graph [math]\displaystyle{ G(V,E) }[/math]is called an [math]\displaystyle{ \alpha }[/math]-min-cut if [math]\displaystyle{ |C|\le\alpha|C^*| }[/math] where [math]\displaystyle{ C^* }[/math] is a min-cut in [math]\displaystyle{ G }[/math].

Give an analysis to lower bound the probability that a single iteration of Karger's Random Contraction algorithm returns an [math]\displaystyle{ \alpha }[/math]-min-cut in a graph [math]\displaystyle{ G(V,E) }[/math] of [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] edges.

Problem 4

Freivalds' Theorem
Let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ n\times n }[/math] matrix such that [math]\displaystyle{ A\neq\boldsymbol{0} }[/math]. For a uniformly random [math]\displaystyle{ r \in\{0, 1\}^n }[/math],
[math]\displaystyle{ \Pr[Ar = \boldsymbol{0}]\le \frac{1}{2} }[/math].
Schwartz-Zippel Theorem
Let [math]\displaystyle{ f\in\mathbb{F}[x_1,x_2,\ldots,x_n] }[/math] be a multivariate polynomial of degree [math]\displaystyle{ d }[/math] over a field [math]\displaystyle{ \mathbb{F} }[/math] such that [math]\displaystyle{ f\not\equiv 0 }[/math]. Fix any finite set [math]\displaystyle{ S\subset\mathbb{F} }[/math], and let [math]\displaystyle{ r_1,r_2\ldots,r_n }[/math] be chosen uniformly and independently at random from [math]\displaystyle{ S }[/math]. Then
[math]\displaystyle{ \Pr[f(r_1,r_2,\ldots,r_n)=0]\le\frac{d}{|S|}. }[/math]

Prove that Schwartz-Zippel Theorem implies Freivalds Theorem.