随机算法 \ 高级算法 (Fall 2016)/Problem Set 3: Difference between revisions
imported>Etone Created page with "== Problem 1== Let <math>Q(x_1,x_2,\ldots,x_n)</math> be a multivariate polynomial over a field <math>\mathbb{Z}_2</math> with the degree sequence <math>(d_1,d_2,\ldots,d_n)</..." |
imported>Etone |
||
| Line 1: | Line 1: | ||
== Problem 1== | == Problem 1== | ||
The Schwartz-Zippel theorem works well for large enough fields <math>\mathbb{F}</math>, but works poorly for fields of small size, such as the [https://en.wikipedia.org/wiki/GF(2) '''binary field'''] <math>\mathbb{Z}_2</math>. | |||
Let <math>Q(x_1,x_2,\ldots,x_n)</math> be a multivariate polynomial over a field <math>\mathbb{Z}_2</math> with the degree sequence <math>(d_1,d_2,\ldots,d_n)</math>. A degree sequence is defined as follows: let <math>d_1</math> be the maximum exponent of <math>x_1</math> in <math>Q</math>, and <math>Q_1(x_2,\ldots,x_n)</math> be the coefficient of <math>x_1^{d_1}</math> in <math>Q</math>; then let <math>d_2</math> be the maximum exponent of <math>x_2</math> in <math>Q_1</math>, and <math>Q_2(x_3,\ldots,x_n)</math> be the coefficient of <math>x_2^{d_2}</math> in <math>Q_1</math>; and so on. | Let <math>Q(x_1,x_2,\ldots,x_n)</math> be a multivariate polynomial over a field <math>\mathbb{Z}_2</math> with the degree sequence <math>(d_1,d_2,\ldots,d_n)</math>. A degree sequence is defined as follows: let <math>d_1</math> be the maximum exponent of <math>x_1</math> in <math>Q</math>, and <math>Q_1(x_2,\ldots,x_n)</math> be the coefficient of <math>x_1^{d_1}</math> in <math>Q</math>; then let <math>d_2</math> be the maximum exponent of <math>x_2</math> in <math>Q_1</math>, and <math>Q_2(x_3,\ldots,x_n)</math> be the coefficient of <math>x_2^{d_2}</math> in <math>Q_1</math>; and so on. | ||
Let <math>S_1,S_2,\ldots,S_n\subseteq\mathbb{Z}_2</math> be arbitrary finite subsets. For <math>r_i\in S_i</math> chosen independently and uniformly at random, show that | Let <math>S_1,S_2,\ldots,S_n\subseteq\mathbb{Z}_2</math> be arbitrary finite subsets. For <math>r_i\in S_i</math> chosen independently and uniformly at random, show that | ||
:<math>\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>. | :<math>\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>. | ||
Revision as of 15:05, 23 November 2016
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].