Game-Theoretic Techniques

Prev: Introduction Next: Moments and Deviations

Problems

2.1

Show that for any deterministic evaluation algorithm, there is an instance of $T_{d,k}$ that forces the algorithm to read the values on all $d^{2k}$ leaves.

---

2.2

Generalize the randomized algorithm and analysis of Section 2.1 to trees $T_{d,k}$ for $d>2$.

---

2.3

Due to R. Boppana [362].

Consider a uniform rooted tree of height $h$; every leaf is at distance $h$ from the root. The root, as well as any internal node, has three children. Each leaf has a Boolean value associated with it. Each internal node returns the value returned by the majority of its children. The evaluation problem consists of determining the value of the root; at each step, an algorithm can choose one leaf whose value it wishes to read.

1. Show that for any deterministic algorithm, there is an instance, a set of Boolean values for the leaves, that forces it to read all $n=3^h$ leaves.
2. Consider the recursive randomized algorithm that evaluates two sub-trees of the root chosen at random. If the values returned disagree, it proceeds to evaluate the third sub-tree. Show that the expected number of leaves read by this algorithm, on any instance, is at most $n^{0.9}$.

---

2.4

Determine the value $V_R$ of the following $2\times 2$ matrix game and give optimal mixed strategies for the two players.

$$\left(\begin{array}{cc}5& 6\\ 7& 4\end{array}\right)$$

---

2.5

Due to R. M. Karp.

Let $(a_{ij})$ be an $m\times n$ matrix, let the vector $(p_1,p_2,\dots ,p_m)$ consist of reals in $[0,1]$ such that

$$\sum _{i=1}^m{p}_i=1,$$

and let $(q_1,q_2,\dots ,q_n)$ consist of reals in $[0,1]$ such that

$$\sum _{j=1}^n{q}_j=1.$$

Prove algebraically that

$$\underset{q}{\max }\underset{i}{\min }\sum _{j=1}^n{a}_{ij}{q}_j\le \underset{p}{\min }\underset{j}{\max }\sum _{i=1}^m{p}_i{a}_{ij}.$$

---

2.6

Use Yao’s Minimax Principle to prove a lower bound on the expected running time of any Las Vegas algorithm for sorting $n$ numbers.

---

2.7

Due to R. M. Karp.

You are given an array $A$ containing $n$ numbers in sorted order. In one step, an algorithm may specify an integer $i\in [1,n]$, and is given the value of $A[i]$ in return. Determine lower and upper bounds on the expected number of steps taken by a Las Vegas randomized algorithm to determine whether or not a given key $k$ is present in the array.

---

2.8

Due to R. M. Karp.

In a graph with $n$ vertices, where $n$ is even, a perfect matching is a set of $n/2$ edges, no two of which meet at a common vertex. Consider a randomized algorithm that takes an $n$-vertex graph as input and correctly determines whether the graph has a perfect matching. At each step the algorithm asks a question of the form “Is there an edge between vertex $i$ and vertex $j$?” The complexity of the algorithm is defined as the maximum, over all $n$-vertex graphs $G$, of the expected number of questions $C(n)$ asked when the input graph is $G$. Prove:

$$C(n)=\Omega (n^2).$$

---

2.9

Due to R. M. Karp.

Give lower bounds on the expected number of steps for Las Vegas algorithms for the following problems:

1. Given a string of $n$ bits, the algorithm must determine whether the string contains three consecutive $1$s. In one step, it is allowed to inspect one bit of the string. All other computation is free.
2. Given a graph on $n$ vertices, the algorithm must determine whether the graph contains a vertex of degree $0$. In one step, it specifies two vertices and is told whether there is an edge between the specified vertices, just as in Problem 2.8. All other computation is free.

---

2.10

Due to R. M. Karp.

Given a list of $n$ values $v_1,v_2,\dots ,v_n$, the majority element problem is to determine the index $i$, if one exists, such that the value $v_i$ occurs more than $n/2$ times in the list. Determine lower and upper bounds on the expected running time of any Las Vegas algorithm that solves the majority element problem under the assumption that the algorithm can at each step specify two indices, and is told whether or not the corresponding list entries are equal.

---

2.11

What happens to the proof of Theorem 2.9 if in the second condition in the definition of a randomized circuit we were to replace “at least half” by “at least $1/k$ for $k>2$“?

---

2.12

Show that

$$BPP\subseteq P/\mathrm{poly}.$$