高级算法 (Fall 2022)/Problem Set 4

Problem 1

Suppose there is a coin [math]\displaystyle{ C }[/math]. During each query, it outputs HEAD with probability [math]\displaystyle{ p }[/math] and TAIL with probability [math]\displaystyle{ 1-p }[/math], where [math]\displaystyle{ p \in (0, 1) }[/math] is a real number.

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

Problem 2

A boolean code is a mapping [math]\displaystyle{ C:\{0,1\}^k\rightarrow\{0,1\}^n }[/math]. Each [math]\displaystyle{ x\in\{0,1\}^k }[/math] is called a message and [math]\displaystyle{ y=C(x) }[/math] is called a codeword. The code rate [math]\displaystyle{ r }[/math] of a code [math]\displaystyle{ C }[/math] is [math]\displaystyle{ r=\frac{k}{n} }[/math]. A boolean code [math]\displaystyle{ C:\{0,1\}^k\rightarrow\{0,1\}^n }[/math] is a linear code if it is a linear transformation, i.e. there is a matrix [math]\displaystyle{ A\in\{0,1\}^{n\times k} }[/math] such that [math]\displaystyle{ C(x)=Ax }[/math] for any [math]\displaystyle{ x\in\{0,1\}^k }[/math], where the additions and multiplications are defined over the finite field of order two, [math]\displaystyle{ (\{0,1\},+_{\bmod 2},\times_{\bmod 2}) }[/math].

The distance between two codeword [math]\displaystyle{ y_1 }[/math] and [math]\displaystyle{ y_2 }[/math], denoted by [math]\displaystyle{ d(y_1,y_2) }[/math], is defined as the Hamming distance between them. Formally, [math]\displaystyle{ d(y_1,y_2)=\|y_1-y_2\|_1=\sum_{i=1}^n|y_1(i)-y_2(i)| }[/math]. The distance of a code [math]\displaystyle{ C }[/math] is the minimum distance between any two codewords. Formally, [math]\displaystyle{ d=\min_{x_1,x_2\in \{0,1\}^k\atop x_1\neq x_2}d(C(x_1),C(x_2)) }[/math].

Usually we want to make both the code rate [math]\displaystyle{ r }[/math] and the code distance [math]\displaystyle{ d }[/math] as large as possible, because a larger rate means that the amount of actual message per transmitted bit is high, and a larger distance allows for more error correction and detection.

• Use the probabilistic method to prove that there exists a boolean code [math]\displaystyle{ C:\{0,1\}^k\rightarrow\{0,1\}^n }[/math] of code rate [math]\displaystyle{ r }[/math] and distance [math]\displaystyle{ \left(\frac{1}{2}-\Theta\left(\sqrt{r}\right)\right)n }[/math]. Try to optimize the constant in [math]\displaystyle{ \Theta(\cdot) }[/math].
• Prove a similar result for linear boolean codes.

Problem 3

Let [math]\displaystyle{ G=(V,E) }[/math] be a cycle of length [math]\displaystyle{ 4n }[/math], and let [math]\displaystyle{ V=V_1 \cup V_2 \cup ... \cup V_n }[/math] be a paitition of its [math]\displaystyle{ 4n }[/math] vertices into [math]\displaystyle{ n }[/math] pairwise disjoint subsets, each of cardinality [math]\displaystyle{ 4 }[/math]. Is it true that there must be an independent set of $G</math> containing precisely one vertex from each [math]\displaystyle{ V_i }[/math]? Prove or supply a counterexample.