Algebraic Techniques

Prev: Markov Chains and Random Walks Next: Data Structures

Problems

7.1

In this problem we will see that Theorem 7.1 is actually just a special case of Theorem 7.2. In the setting of Theorem 7.1, construct a multivariate polynomial $Q$ such that $Q\equiv 0$ if and only if $AB=C$, and then apply Theorem 7.2 to derive the result in Theorem 7.1.

---

7.2

Two rooted trees $T_1$ and $T_2$ are said to be isomorphic if there exists a one-to-one onto mapping $f$ from the vertices of $T_1$ to those of $T_2$ satisfying the following condition: for each internal vertex $v$ of $T_1$ with the children $v_1,\dots ,v_k$, the vertex $f(v)$ has as children exactly the vertices $f(v_1),\dots ,f(v_k)$. Observe that no ordering is assumed on the children of any internal vertex. Devise an efficient randomized algorithm for testing the isomorphism of rooted trees and analyze its performance.

Hint: Associate a polynomial $P_v$ with each vertex $v$ in a tree $T$. The polynomials are defined recursively, the base case being that the leaf vertices all have $P=x_0$. An internal vertex $v$ of height $h$ with the children $v_1,\dots ,v_k$ has its polynomial defined to be

$$(x_h-P_{v_1})(x_h-P_{v_2})\cdots (x_h-P_{v_k}).$$

Note that there is exactly one indeterminate for each level in the tree.

Remark: There is a linear time deterministic algorithm for this problem based on a similar approach. Refer to Aho, Hopcroft and Ullman [5].

---

7.3

Due to M. Blum, A.K. Chandra, and M.N. Wegman [64].

A labeled directed acyclic graph $G(V,E)$ may be used to represent a Boolean function of $n$ variables $x_1,\dots ,x_n$, as follows. One vertex of $V$ is the start vertex, and another the finish vertex. Every vertex has out-degree zero or two; if two edges leave a vertex, one must be labeled with a variable and the other by the complement of this variable. Such a graph is said to be free if there is at most one occurrence of every variable, complemented or not, on any (directed) path of $G$. The Boolean function represented by such a graph is the sum of all product terms, where each product term is a product of all the variables on a path from the start vertex to the finish vertex.

Devise a randomized algorithm that, given two free graphs, decides whether they represent the same Boolean function. If the functions are different, the algorithm should output NO; otherwise, it should output YES with probability at least $1/2$.

---

7.4

Due to R.J. Lipton [277]; see also M. Blum and S. Kannan [66].

Consider the problem of deciding whether two integer multisets $S_1$ and $S_2$ are identical in the sense that each integer occurs the same number of times in both sets. This problem can be solved by sorting the two sets in $O(n\log n)$ time, where $n$ is the cardinality of the multisets. Suggest a way of representing this as a problem involving a verification of a polynomial identity, and thereby obtain an efficient randomized algorithm. Discuss the relative merits of the two algorithms, keeping in mind issues such as the model of computation and the size of the integers being operated upon. See also Problem 8.20.

---

7.5

Due to J. Naor.

Two $n\times n$ matrices $A$ and $B$ over the field ${\mathbb{Z}}_2$ are said to be similar if there exists a non-singular matrix $T$ such that $TA{T}^{-1}=B$. Devise a randomized algorithm for testing the similarity of the matrices $A$ and $B$.

Hint: View the entries in $T$ as a collection of variables, and from the definition of similarity, obtain a homogeneous set of linear equations that these variables must satisfy. Any solution $T$ must be a linear combination of the basic solutions to this family of equations. Apply the randomized techniques from this chapter to determining whether there exists a linear combination of the basic solutions that yields a non-singular matrix $T$.

---

7.6

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

Let $S_1,S_2,\dots ,S_n\subseteq \mathbb{F}$ be arbitrary subsets. For $r_i\in S_i$ chosen independently and uniformly at random, show that

$$\mathrm{Pr}[Q(r_1,r_2,\dots ,r_n)=0\mid Q\ne 0]\le \left(\frac{d_1}{|S_1|}+\frac{d_2}{|S_2|}+\cdots +\frac{d_n}{|S_n|}\right).$$

---

7.7

Due to J. Edmonds [134].

Let $G(U,V,E)$ be a bipartite graph, and let $A$ be the corresponding matrix of indeterminates as defined in Section 7.3. Show that the size of a maximum matching in $G$ is exactly equal to the rank of the matrix $A$.

---

7.8

Tutte’s Theorem [398].

In this problem we generalize Theorem 7.3 to the case of an arbitrary (possibly non-bipartite) graph $G(V,E)$ where $V=\{v_1,\dots ,v_n\}$. A skew-symmetric matrix $A$ is defined to be a matrix in which for all $i$ and $j$, $A_{ij}=-A_{ji}$. Let $A$ be the $n\times n$ skew-symmetric matrix obtained from $G(V,E)$ as follows. A distinct indeterminate $x_{ij}$ is associated with the edge $(v_i,v_j)$, where $i<j$, and the corresponding matrix entries are given by $A_{ij}=x_{ij}$ and $A_{ji}=-x_{ij}$; more succinctly,

$$A_{ij}=\{\begin{array}{ll}{x}_{ij}& (v_i,v_j)\in E\text{ and }i<j\\ -x_{ji}& (v_i,v_j)\in E\text{ and }i>j\\ 0& \text{otherwise}\end{array}$$

This matrix is called the Tutte matrix of the graph $G$. Define the multivariate polynomial $Q(x_{11},x_{12},\dots ,x_{nn})$ as being equal to $\det (A)$. Show that $G$ has a perfect matching if and only if $Q\ne 0$.

---

7.9

Due to M.O. Rabin and V.V. Vazirani [348, 349].

Consider the Tutte matrix of a (non-bipartite) graph $G(V,E)$ defined in Problem 7.8. Show that the rank of the Tutte matrix of $G$ is twice the size of a maximum matching in $G$.

Hint: Let $A$ be an $n\times n$ skew-symmetric matrix of rank $r$. For any two sets $S,T\subseteq \{1,\dots ,n\}$, denote by $A_{ST}$ the sub-matrix of $A$ obtained by including only the rows with indices in $S$ and columns with indices in $T$. Then, for any two sets $S,T\subseteq \{1,\dots ,n\}$ of size $r$,

$$\det (A_{SS})\times \det (A_{TT})=\det (A_{ST})\times \det (A_{TS}).$$

---

7.10

Given a randomized algorithm for testing the existence of a perfect matching in a graph $G$, describe how you would actually construct such a matching. Assuming that you use the randomized testing algorithm from Problem 7.8, compare the running time of your approach with that of the best known deterministic algorithm for perfect matching mentioned in the Notes section.

---

7.11

Given a randomized algorithm for testing the existence of a perfect matching in a graph, describe how we can use this to construct a maximum matching in a graph $G$.

---

7.12

Due to R.M. Karp and M.O. Rabin [249].

In this problem we will use a different fingerprinting technique to solve the pattern matching problem. The idea is to map any bit string $s$ into a $2\times 2$ matrix $M(s)$, as follows.

• For the empty string $ϵ$,

$$M(ϵ)=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right].$$

• $M(0)=$

$$\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right].$$

• $M(1)=$

$$\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right].$$

• For non-empty strings $x$ and $y$, $M(xy)=M(x)\times M(y)$.

Show that this fingerprint function has the following properties.

1. $M(x)$ is well-defined for all $x\in \{0,1{\}}^{\ast }$.
2. $M(x)=M(y)\Rightarrow x=y$.
3. For $x\in \{0,1{\}}^n$, the entries in $M(x)$ are bounded by Fibonacci number $F_n$ (see Appendix B).

By considering the matrices $M(x)$ modulo a suitable prime $p$, show how you would perform efficient randomized pattern matching. Explain how you would implement this as a “real-time” algorithm.

---

7.13

Due to R.M. Karp and M.O. Rabin [249].

Consider the two-dimensional version of the pattern matching problem. The text is an $n\times n$ matrix $X$, and the pattern is an $m\times m$ matrix $Y$. A pattern match occurs if $Y$ appears as a (contiguous) sub-matrix of $X$. To apply the randomized algorithm described above, we convert the matrix $Y$ into an $m^2$-bit vector using the row-major format. The possible occurrences of $Y$ in $X$ are the $m^2$-bit vectors $X(j)$ obtained by taking all $(n-m+1{)}^2$ sub-matrices of $X$ in a row-major form. It is clear that the earlier algorithm can now be applied to this scenario. Analyze the error probability in this case, and explain how the fingerprints of each $X(j)$ can be computed at a small incremental cost.

---

7.14

Prove the following relations directly from the definition of $IP$, i.e., without invoking any results regarding $IP$ stated in this chapter.

(a) Show that $NP\subseteq IP$.

(b) Show that if the definition of $IP$ is modified to require that the probability of error be zero, then the resulting complexity class would be exactly the class $NP$.

(c) Show that $\text{co-}RP\subseteq IP$.

---

7.15

Prove Lemma 7.9.

---

7.16

Due to C.H. Papadimitriou [324].

Let $PSPACE$ be the class of all languages whose membership can be decided using space polynomial in the input size, with no explicit constraint on the running time. Show that $IP\subseteq PSPACE$.

---

7.17

Due to A. Shamir [372].

A quantified Boolean formula (QBF) is a Boolean formula $\Phi$ of the form

$$(Q_1{x}_1)(Q_2{x}_2)\cdots (Q_n{x}_n)F(x_1,x_2,\dots ,x_n),$$

where each $x_i$ is a Boolean variable, each $Q_i$ is either the universal $(\forall )$ or the existential $(\exists )$ quantifier, and $F$ is quantifier-free Boolean formula. It is known that QBF is $PSPACE$-complete. By devising an interactive proof system for QBF, show that $PSPACE\subseteq IP$.

Hint: The following is a brief sketch of a reformulation of Shamir’s proof as presented by A. Shen. The first step is to arithmetize the QBF formula $\Phi$. For any Boolean expression $G$, possibly a single Boolean variable or a quantified formula, construct an integer polynomial $\hat{G}$ using the following rules recursively: replace TRUE by $1$ and FALSE by $0$; replace Boolean variables $x_i$ by arithmetic variables ${\hat{x}}_i$; replace $P\wedge Q$ by $\hat{P}\times \hat{Q}$; replace the negation of an expression $P$ by $1-\hat{P}$; replace $P\vee Q$ by $\hat{P}+\hat{Q}-(\hat{P}\times \hat{Q})$; replace $(\forall x_i)P(x_i)$ by $\hat{P}(0)\times \hat{P}(1)$; and replace $(\exists x_i)P(x_i)$ by $\hat{P}(0)+\hat{P}(1)-(\hat{P}(0)\times \hat{P}(1))$. Apply the ideas used in devising an interactive proof system for the arithmetized version of #3SAT to the problem of verifying the value of the arithmetized version, $\hat{\Phi }$, of the QBF formula $\Phi$. One serious problem in the case of QBF is that the intermediate polynomials need not be of a small degree, primarily due to the arithmetization of the quantifiers. To handle this problem, assume that the arithmetization of the sequence of quantifiers $Q_1,\dots ,Q_n$ is interleaved with the application of the following reduce operation: for each (integer) variable ${\hat{x}}_i$, replace any non-zero power ${\hat{x}}_i^k$ by ${\hat{x}}_i$. Argue that in the case where we assign only the values $0$ or $1$ to each ${\hat{x}}_i$, the reduce operation does not change the value of the resulting polynomial.

Remark: Combining this result with that of Problem 7.16, we conclude that $IP=PSPACE$. It is known that $PSPACE$ is closed under complementation, and so it follows that $IP=\text{co-}IP$.

---

7.18

Due to L. Fortnow, J. Rompel, and M. Sipser [153].

Define the complexity class $MIP$ as the generalization of $IP$ where the verifier has access to two provers and the provers are not allowed to communicate with each other once the verifier starts executing. Show that $MIP=PCP$.

---

7.19

Prove the following relations directly from the definition of $PCP$, i.e., without invoking any results regarding $PCP$ stated in this chapter.

(a) Show that $P=PCP[0,0]$.

(b) Show that $NP=PCP[0,\mathrm{poly}(n)]$.

(c) Show that $\text{co-}RP=PCP[\mathrm{poly}(n),0]$.

---

7.20

Due to S. Arora and S. Safra [33].

Show that $PCP[\log n,1]\subseteq NP$.

---

7.21

Prove Lemma 7.11.

---

7.22

Consider a multivariate function $f(x):{\mathbb{Z}}_2^n\to {\mathbb{Z}}_2$. Show that $f$ is linear if and only if for all $a$ and $b$,

$$f(a)+f(b)=f(a+b).$$

---

7.23

This problem is concerned with some properties of the distance measure defined in Definition 7.7.

(a) Show that the distance measure $\Delta$ satisfies the triangle inequality: for all functions $f,g,h:I\to O$,

$$\Delta (f,h)\le \Delta (f,g)+\Delta (g,h).$$

(b) For a class of functions $F=\{f:I\to O\}$, define ${\Delta }_{\min }(F)$ as the minimum distance between any two functions in $F$. Show that for any function $g$ (not necessarily in $F$), there is at most one function from $F$ at distance ${\Delta }_{\min }(F)/2$ or less.

(c) Suppose that $F$ is the set of all linear functions from ${\mathbb{Z}}_2^n$ to ${\mathbb{Z}}_2$. What is ${\Delta }_{\min }(F)$?

---

7.24

Due to M. Blum, M. Luby, and R. Rubinfeld [68].

Prove Lemma 7.12 using the following sketch of a proof due to D. Coppersmith. Define the function $G$ such that for each $x$,

$$G(x)={\mathrm{majority}}_y[\hat{G}(x+y)-\hat{G}(y)],$$

where the “majority” denotes the value occurring most often over all choices of $y$, breaking ties arbitrarily.

(a) Show that for all $x$, and for $y$ chosen uniformly at random,

$$\mathrm{Pr}[G(x)=\hat{G}(x+y)-\hat{G}(y)]\ge 1-\delta .$$

(b) Show that the functions $G$ and $\hat{G}$ are $\delta$-close.

(c) Show that $G$ is a linear function.

(d) Show that $G$ is uniquely defined.

---

7.25

Prove Lemma 7.13.

---

7.26

Appropriately generalizing Lemma 7.13, describe how the verifier can check that $c=a\circ b$.