随机算法 \ 高级算法 (Fall 2016)/Problem Set 3

Problem 1

The Schwartz-Zippel theorem works well for large enough fields [math]\displaystyle{ \mathbb{F} }[/math], but works poorly for fields of small size, such as the binary field [math]\displaystyle{ \mathbb{Z}_2 }[/math].

Let [math]\displaystyle{ Q(x_1,x_2,\ldots,x_n) }[/math] be a multivariate polynomial over a field [math]\displaystyle{ \mathbb{Z}_2 }[/math] with the degree sequence [math]\displaystyle{ (d_1,d_2,\ldots,d_n) }[/math]. A degree sequence is defined as follows: let [math]\displaystyle{ d_1 }[/math] be the maximum exponent of [math]\displaystyle{ x_1 }[/math] in [math]\displaystyle{ Q }[/math], and [math]\displaystyle{ Q_1(x_2,\ldots,x_n) }[/math] be the coefficient of [math]\displaystyle{ x_1^{d_1} }[/math] in [math]\displaystyle{ Q }[/math]; then let [math]\displaystyle{ d_2 }[/math] be the maximum exponent of [math]\displaystyle{ x_2 }[/math] in [math]\displaystyle{ Q_1 }[/math], and [math]\displaystyle{ Q_2(x_3,\ldots,x_n) }[/math] be the coefficient of [math]\displaystyle{ x_2^{d_2} }[/math] in [math]\displaystyle{ Q_1 }[/math]; and so on.

Let [math]\displaystyle{ S_1,S_2,\ldots,S_n\subseteq\mathbb{Z}_2 }[/math] be arbitrary finite subsets. For [math]\displaystyle{ r_i\in S_i }[/math] chosen independently and uniformly at random, show that

[math]\displaystyle{ \Pr\left[Q(r_1,r_2,\ldots,r_n)=0\mid Q\not\equiv 0\right]\le\sum_{i=1}^n\frac{d_i}{|S_i|} }[/math].

Problem 2

In Balls-and-Bins model, we throw [math]\displaystyle{ m }[/math] balls independently and uniformly at random into [math]\displaystyle{ n }[/math] bins. We know that the maximum load is [math]\displaystyle{ \Theta\left(\frac{\log n}{\log\log n}\right) }[/math] with high probability when [math]\displaystyle{ m=\Theta(n) }[/math]. The two-choice paradigm is another way to throw [math]\displaystyle{ m }[/math] balls into [math]\displaystyle{ n }[/math] bins: each ball is thrown into the least loaded of two bins chosen independently and uniformly at random(it could be the case that the two chosen bins are exactly the same, and then the ball will be thrown into that bin), and breaks the tie arbitrarily. When [math]\displaystyle{ m=\Theta(n) }[/math], the maximum load of two-choice paradigm is known to be [math]\displaystyle{ \Theta(\log\log n) }[/math] with high probability, which is exponentially less than the maxim load when there is only one random choice. This phenomenon is called the power of two choices.

Here are the questions:

• Consider the following paradigm: we throw [math]\displaystyle{ n }[/math] balls into [math]\displaystyle{ n }[/math] bins. The first [math]\displaystyle{ \frac{n}{2} }[/math] balls are thrown into bins independently and uniformly at random. The remaining [math]\displaystyle{ \frac{n}{2} }[/math] balls are thrown into bins using the two-choice paradigm. What is the maximum load with high probability? You need to give an asymptotically tight bound (in the form of [math]\displaystyle{ \Theta(\cdot) }[/math]).

• Replace the above paradigm to the following: the first [math]\displaystyle{ \frac{n}{2} }[/math] balls are thrown into bins using the two-choice paradigm while the remaining [math]\displaystyle{ \frac{n}{2} }[/math] balls are thrown into bins independently and uniformly at random. What is the maximum load with high probability in this case? You need to give an asymptotically tight bound.

• Replace the above paradigm to the following: assume all [math]\displaystyle{ n }[/math] balls are thrown in a sequence. For every [math]\displaystyle{ 1\le i\le n }[/math], if [math]\displaystyle{ i }[/math] is odd, we throw [math]\displaystyle{ i }[/math]-th ball into bins independently and uniformly at random, otherwise, we throw it into bins using the two-choice paradigm. What is the maximum load with high probability in this case? You need to give an asymptotically tight bound.