# Prerequisite Definitions

Alphabets $$\Sigma$$, and $$\Gamma$$ are finite nonempty sets of symbols.

A string is a finite sequence of zero or more symbols from an alphabet.

$$\Sigma^\star$$ is the set of all strings over alphabet $$\Sigma$$.

$$\epsilon$$ is the empty string and cannot be in $$\Sigma$$.

A problem is a mapping from strings to strings.

A decision problem is a problem whose output is yes/no (or often accept/reject).

A decision problem be thought of as the set of all strings for which the function outputs “accept”.

A language is a set of strings, so any set $$S \subseteq \Sigma^\star$$ is a language, even $$\emptyset$$. Thus, decision problems are equivalent to languages.

# Regular Languages

$$L(M)$$ is the language accepted by machine $$M$$.

A deterministic finite automaton is a 5-tuple $$M = (Q, \Sigma, \delta, q_0, F)$$, where

• $$Q$$ is a finite set of states,

• $$\Sigma$$ is an alphabet,

• $$\delta : Q \times \Sigma \rightarrow Q$$ is a transition function describing its transitions and labels,

• $$q_0 \in Q$$ is the starting state, and

• $$F \subseteq Q$$ is a set of accepting states.

If $$\delta$$ is not fully specified, we assume an implicit transition to an error state.

A deterministic finite automaton $$M$$ accepts input string $$w = w_1w_2 \dots w_n$$ ($$w_i \in \Sigma$$) if there exists a sequence of states $$r_0, r_1, r_2, \dots, r_n$$ ($$r_i \in Q$$) such that

• $$r_0 = q_0$$,

• for all $$i \in \{1, \dots, n\}$$, $$r_i = \delta(r_{i-1}, w_i)$$, and

• $$r_n \in F$$.

$$r_0, r_1, r_2, \dots, r_n$$ are the sequence of states visited during the machine’s computation.

A non-deterministic finite automaton is a 5-tuple $$M = (Q, \Sigma, \delta, q_0, F)$$, where

• $$Q, \Sigma, q_0, F$$ are the same as a deterministic finite automaton’s, and

• $$\delta : Q \times (\Sigma \cup \{\epsilon\}) \rightarrow 2^Q$$.

A non-deterministic finite automaton accepts the string $$w = w_1w_2 \dots w_n$$ ($$w_i \in \Sigma$$) if there exist a string $$y = y_1y_2 \dots y_m$$ ($$y_i \in \Sigma \cup \{\epsilon\}$$) and a sequence $$r = r_0, r_1, \dots, r_n$$ ($$r_i \in Q$$) such that

• $$w = y_1 \circ y_2 \circ \cdots \circ y_m$$ (i.e. $$y$$ is $$w$$ with some $$\epsilon$$ inserted),

• $$r_0 = q_0$$,

• for all $$i = \{1, \dots, m\}$$, $$r_i \in \delta(r_{i-1}, q_i)$$, and

• $$r_m \in F$$.

The $$\epsilon$$-closure for any set $$S \subseteq Q$$ is denoted $$E(S)$$, which is the set of all states in $$Q$$ that can be reachable by following any number of $$\epsilon$$-transition.

A non-deterministic finite automaton can be converted to an equivalent deterministic finite automaton.

A regular language is any language accepted by some finite automaton. The set of all regular languages is called the class of regular languages.

Regular languages are closed under

• Concatenation $$L_1 \circ L_2 = \{x \circ y : x \in L_1 \text{ and } y \in L_2\}$$. Note: $$L_1 \not\subseteq L_1 \circ L_2$$.

• Union $$L_1 \cup L_2 = \{x : x \in L_1 \text{ or } x \in L_2\}$$.

• Intersection $$L_1 \cap L_2 = \{x : x \in L_1 \text{ and } x \in L_2\}$$.

• Complement $$\overline{L} = \Sigma^\star \setminus L = \{x : x \notin L\}$$.

• Star $$L^\star = \{x_1 \circ x_2 \circ \cdots \circ x_k : x_i \in L \text{ and } k \geq 0\}$$.

$$R$$ is a regular expression if $$R$$ is

• $$a \in \Sigma$$,

• $$\epsilon$$,

• $$\emptyset$$,

• $$R_1 \cup R_2$$, or $$R_1 | R_2$$,

• $$R_1 \circ R_2$$, or $$R_1R_2$$,

• $$R_1^\star$$,

• Shorthand: $$\Sigma = (a_1 | a_2 | \dots | a_k)$$, $$a_i \in \Sigma$$,

where $$R_i$$ is a regular expression.

Identities of Regular Languages

• $$\emptyset \cup R = R \cup \emptyset = R$$

• $$\emptyset \circ R = R \circ \emptyset = \emptyset$$

• $$\epsilon \circ R = R \circ \epsilon = R$$

• $$\epsilon^\star = \epsilon$$

• $$\emptyset^\star = \emptyset$$

• $$\emptyset \cup R \circ R^\star = R \circ R^\star \cup \epsilon = R^\star$$

• $$(a | b)^\star = (a^\star | b^\star)^\star = (a^\star b^\star)^\star = (a^\star | b)^\star = (a | b^\star)^\star = a^\star(ba^\star)^\star = b^\star(ab^\star)^\star$$

Languages accepted by DFAs = languages accepted by NFAs = regular languages

If $$L$$ is a finite language, $$L$$ is regular.

If a computation path of any finite automaton is longer than the number of states it has, there must be a cycle in that computation path.

Every regular language satisfies the pumping condition.

Pumping condition: There exists an integer $$p$$ such that for every string $$w \in L$$, with $$|w| \geq p$$, there exist strings $$x, y, z \in \Sigma^\star$$ with $$w = xyz, y \neq \epsilon, |xy| \leq p$$ such that for all $$i \geq 0$$, $$xy^iz \in L$$.

Negation of pumping condition: For all integers $$p$$, there exists a string $$w \in L$$, with $$|w| \geq p$$, for all $$x, y, z \in \Sigma^\star$$ with $$w = xyz, y \neq \epsilon, |xy| \leq p$$, there exists $$i \geq 0, i \neq 1$$ such that $$xy^iz \notin L$$.

Limitations of finite automata:

• Only read input once, left to right.

• Only finite memory.

# Context-Free Languages

A pushdown automaton is a 6-tuple $$M = (Q, \Sigma, \Gamma, \delta, q_0, F)$$, where

• $$Q$$ is a finite set of states,

• $$\Sigma$$ is its input alphabet,

• $$\Gamma$$ is its stack alphabet,

• $$\delta : Q \times (\Sigma \cup \{\epsilon\}) \times (\Gamma \cup \{\epsilon\}) \rightarrow 2^{Q \times (\Gamma \cup \{\epsilon\})}$$ is its transition function,

• $$q_0 \in Q$$ is its starting state, and

• $$F \subseteq Q$$ is a finite set of accepting states.

Labels: $$a, b \rightarrow c$$: if input symbol is $$a$$, and top of stack is $$b$$, pop it and push $$c$$. In other words, input symbol read, stack symbol popped $$\rightarrow$$ stack symbol pushed, e.g. $$0, \epsilon \rightarrow \$$.

Suppose $$u, v, w$$ are strings of variables and terminals, and there is a rule $$A \rightarrow w$$. From the string $$uAv$$, we can obtain $$uwv$$. We write $$uAv \rightarrow uwv$$, and say $$uAv$$ yields $$uwv$$.

If $$u_1 \rightarrow u_2 \rightarrow \dots \rightarrow u_k$$, then $$u_1 \rightarrow^\star u_k$$, or $$u_1$$ derives $$u_k$$. There must be a finite number of arrows between $$u_1$$ and $$u_k$$.

Given a grammar $$G$$, the language derived by the grammar is $$L(G) = \{w \in \Sigma^\star : S \rightarrow^\star w \text{ and } S \text{ is the start variable}\}$$

Context-free grammar: the lhs of rules is a single variable, rhs is any string of variables and terminals. A context-free language is one that can be derived from a context-free grammar. An example context-free grammar is $$G = (V, \Sigma, R, \langle \texttt{EXPR} \rangle)$$, where $$V = \{\langle \texttt{EXPR} \rangle, \langle \texttt{TERM} \rangle, \langle \texttt{FACTOR} \rangle\}$$, $$\Sigma = \{a, +, \times, (, )\}$$, and $$R = \{\langle \texttt{EXPR} \rangle \rightarrow \langle \texttt{EXPR} \rangle + \langle \texttt{TERM} \rangle | \langle \texttt{TERM} \rangle, \langle \texttt{TERM} \rangle \rightarrow \langle \texttt{TERM} \rangle \times \langle \texttt{FACTOR} \rangle | \langle \texttt{FACTOR} \rangle, \langle \texttt{FACTOR} \rangle \rightarrow (\langle \texttt{EXPR} \rangle)\}$$.

A left-most derivation is a sequence $$S \rightarrow u_1 \rightarrow u_2 \rightarrow \dots \rightarrow u_k \rightarrow w$$ where each step applies a rule to the left-most variable. A grammar is ambiguous when it has multiple left-most derivations for the same string.

A language $$L$$ is recognized by a pushdown automaton iff $$L$$ is described by a context-free grammar.

Context-free languages are closed under union, concatenation, star.

# Recognizable Languages

Differences from previous models

• The input is written on tape.

• It can write to the tape.

• It can move left and right on tape.

• It halts immediately when it reaches an accepting or rejecting state. The rejecting state must exist but may not be shown.

A deterministic Turing machine is a 7-tuple $$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$$, where

• $$Q$$ is its finite non-empty set of states,

• $$\Sigma$$ is its input alphabet,

• $$\Gamma$$ is its tape alphabet ($$\Sigma \subset \Gamma$$ and $$\text{\textvisiblespace } \in \Gamma \setminus \Sigma$$),

• $$\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$$ is its transition function,

• $$q_0 \in Q$$ is its starting state,

• $$q_{accept} \in Q$$ is its accepting state, and

• $$q_{reject} \in Q$$ is its rejecting state ($$q_{reject} \neq q_{accept}$$).

Labels: $$a \rightarrow b, R$$: if tape symbol is $$a$$, write $$b$$ and move head right. $$a \rightarrow R$$: if tape symbol is $$a$$, move head right. $$a, b, c \rightarrow R$$: if tape symbol is $$a, b$$, or $$c$$, move head right.

On input $$x$$, a Turing machine can (1) accept, (2) reject, or (3) run in an infinite loop.

The language recognized by a Turing machine $$M$$ is $$L(M) = \{x : \text{on input } x, M \text{ halts in } q_{accept}\}$$. A language is recognizable if there exists a Turing machine which recognizes it.

Regular languages $$\subseteq$$ context-free languages $$\subseteq$$ decidable languages $$\subseteq$$ recognizable languages

A configuration is a way to describe the entire state of the Turing machine. It is a string $$aqb$$ where $$a \in \Gamma^\star, q \in Q, b \in \Gamma^\star$$, which indicates that $$q$$ is the current state of the Turing machine, the tape content currently is $$ab$$ and its head is currently pointing at the first symbol of $$b$$. Any Turing machine halts if its configuration is of the form $$aq_{accept}b$$, or $$aq_{reject}b$$ for any $$ab$$. Config($$i$$) uniquely determines Config($$i + 1$$).

Every $$k$$-tape Turing machine has an equivalent single tape Turing machine.

If the alphabet of the multitape Turing machine is $$\Gamma$$, we can make the single tape Turing machine’s alphabet $$(\Gamma \cup \{\#\}) \times \{\texttt{normal}, \texttt{bold}\}$$.

A non-deterministic Turing machine is a 7-tuple $$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$$, where the only difference from a deterministic Turing machine is the transition function $$delta : Q \times \Gamma \rightarrow 2^{Q \times \Gamma \times \{L, R\}}$$.

A non-deterministic Turing machine accepts its input iff some node in the configuration tree has $$q_{accept}$$. It does not accept its input iff the configuration tree grows forever (infinite loop) or no node in the tree has $$q_{accept}$$.

Acceptance of a non-deterministic Turing machine: input $$w$$ is accepted if there exist configurations $$c_0, c_1, \dots, c_k$$ where

• $$c_0 = q_{start}w$$, and

• $$c_i \Rightarrow c_{i+1}$$ ($$c_{i+1}$$ is a possible configuration from $$c_i$$, following the transition function $$\delta$$).

The outcomes could be

• $$w$$ is accepted, i.e. there exists a node in the tree which is an accepting configuration,

• $$w$$ is explicitly rejected, i.e. the tree is finite but no node is an accepting configuration (all leaves are rejecting configurations), or

• the non-deterministic Turing machine runs forever on $$w$$, i.e. the tree is infinite but no node is an accepting configuration (there might be finite branches terminating in a rejecting configuration in the tree).

A Turing machien is a decider if it halts on all inputs, i.e. it either rejects or accepts all inputs.

Every non-deterministic Turing machine has an equivalent deterministic Turing machine. If that non-deterministic Turing machine is a decider, there is an equivalent deterministic Turing machine decider.

Recognizable languages are closed under union, intersection, concatenation, star.

Implementation level description of a multitape Turing machine for $$L = \{x\#x : x \in \{0, 1\}^\star\}$$:

• Scan the first head to the right until it reads a $$\#$$. Move right. The second head is still at the start of the second tape.

• Repeatedly read symbol from the first tape (reject if the symbol is not $$0$$ or $$1$$), write it to the second tape, and move both heads right, until seeing a blank on the first tape.

• Move the first head left until a $$\#$$ is under it. Replace the symbol with a blank ().

• Move both heads left until they reach the start of their respective tapes (using the $$\$$ sign hack to mark the start of the tape).

• Repeat until seeing a blank on both tapes.

• If the symbols on the two tapes differ, reject.

• Otherwise, move both head right.

$$\langle O \rangle$$ is a string encoding for the object $$O$$.

Cardinality of Sets: two sets $$A$$ and $$B$$ have the same cardinality if there exists a bijection $$f : A \rightarrow B$$.

$$\mathbb{N} = \{1, 2, 3, \dots\}$$ is the set of all natural numbers. A set is finite if it has a bijection to {1..n} for some natural number $$n$$. A set is countably infinite if it has the same cardinality as $$\mathbb{N}$$. A set is countable or at most countable if it is finite or countably infinite.

Any language $$L$$ is countable.

The set of all Turing machines is countable.

The set $$\mathcal{B}$$ of all infinite bit-sequences is not countable.

$$2^{\Sigma^\star}$$ is uncountable.

# Reductions

$$A_{TM} = \{\langle M, w \rangle : M \text{ accepts } w\}$$ and $$HALT_{TM} = \{\langle M, w \rangle : M \text{ halts on input } w\}$$ are recognizable but not decidable.

If $$L$$ and $$\overline{L}$$ are recognizable, then $$L$$ is decidable (and so is $$\overline{L}$$).

$$\overline{A_{TM}}$$ is unrecognizable.

Proof template for undecidability via Turing reduction: Reduce a problem known to be undecidable to that language $$L$$, usually $$A_{TM}$$, i.e. $$A_{TM} \leq_T L$$. Assume a Turing machine decider $$R$$ for $$L$$. Construct $$S$$ that decides $$A_{TM}$$ using $$R$$.

Runtime of a deterministic Turing machine is a function $$f : \mathbb{N} \rightarrow \mathbb{N}$$ given by $$f(n) = max_{x \in \Sigma^\star, |x| = n} (\text{no. of steps of } M \text{ on input } x)$$.

$$TIME(t(n)) = \{\text{language } L : \exists \text{deterministic Turing machine that} \\ \text{decides } L \text{ in time } O(t(n))\}$$.

$$P = \bigcup_{c \geq 0} TIME(n^c)$$

$$EXP = \bigcup_{k \geq 0} TIME(2^{n^k})$$

If $$f : \mathbb{N} \rightarrow \mathbb{N}$$ is reasonable and $$f = \Omega(n\log n)$$ then $$TIME(f(n)) \subset TIME(f(n)^2)$$.

$$P \subset EXP$$

Runtime of a non-deterministic Turing machine is the height of the configuration tree.

$$NTIME(t(n)) = \{\text{language } L : \exists \text{ non-deterministic Turing machine that} \\ \text{decides } L \text{ in time } t(n)\}$$

$$NP = \bigcup_{c > 0} NTIME(n^c)$$, i.e. languages for which it is easy to verify membership.

$$P \subseteq NP$$

$$NP \subseteq EXP$$

Verifier-based definition for $$L \in NP$$: there exists a deterministic polytime Turing machine $$V$$ and a constant $$c$$ such that $$L = \{x \in \Sigma^\star : \exists y \in \Sigma^\star, |y| \leq |x|^c, V \text{ accepts } (x, y)\}$$.

A function is polytime computable if $$f : \Sigma^\star \rightarrow \Sigma^\star$$ if there exists a Turing machine $$M$$ that has $$x$$ as input, runs for time poly($$|x|$$) and halts with $$f(x)$$ written on the tape.

$$f$$ is a polytime reduction from language $$A$$ to language $$B$$, denoted $$A \leq_P B$$ if (1) $$f(A) \subseteq B$$, (2) $$f(\overline{A}) \subseteq \overline{B}$$, and (3) $$f$$ is a polytime computable function.

If $$A \leq_P B$$ and $$B \in P$$ then $$A \in P$$.

A language $$L$$ is $$NP$$-hard if $$A \leq_P L$$ for all $$A \in NP$$. A language $$L$$ is $$NP$$-complete if $$L$$ is $$NP$$-hard and $$L \in NP$$.

If $$P \neq NP$$, then there exists language $$L$$ such that $$L \notin NP$$-complete, $$L \notin P$$, and $$L \in NP$$.

If (1) $$B$$ is $$NP$$-complete, (2) $$C \in NP$$, and (3) $$B \leq_P C$$, then $$C$$ is $$NP$$-complete.

$$CLIQUE$$ is a language whose strings are of the form $$\langle G, k \rangle$$, where $$G = (V, E)$$ is a graph and $$k \in \mathbb{N}$$, for which there exists $$U \subseteq V$$ with $$|U| \geq k$$ such that $$\{u, v\} \in E$$ for all distinct vertices $$u, v \in U$$.

$$CLIQUE$$ is $$NP$$-complete

$$3SAT \leq_P CLIQUE$$

$$3SAT \leq_P MAXCLIQUE$$

Reductions from $$3SAT$$ often involves gadgets:

• Clause gadgets: for the assignemnt to pick a true literal in each clause (a clique must pick a vertex from each group)

• Variable gadget: force assignemnt to set each variable either to true or false but not both (a clique cannot pick both $$x_i$$ and $$\overline{x_i}$$).

$$INDSET$$ is a language whose strings are of the form $$\langle H, k \rangle$$, where $$H = (V, E)$$ is a graph and $$k \in \mathbb{N}$$, for which there exists $$U \subseteq V$$ with $$|U| = k$$ such that $$\forall u, v \in U, \{u, v\} \notin E$$.

$$VERTEX-COVER$$ is a language whose strings are of the form $$\langle H, t \rangle$$, where $$H = (V, E)$$ is a graph and $$t \in \mathbb{N}$$, for which there exists a set $$C \subseteq V$$ with $$|C| \leq t$$ such that $$\forall \{u, v\} \in E$$, either $$u$$, $$v$$ or both is in $$C$$.

Let $$G = (V, E)$$ be a graph. Then $$\overline{G} = (V, \overline{E})$$ where $$\overline{E} = \{\{u, v\} : \{u, v\} \notin E\}$$.

$$U$$ is a clique in $$G$$ iff $$\overline{U} = V \setminus U$$ is a vertex cover in $$\overline{G}$$. This implies $$G$$ has a clique of size $$\geq k$$ iff $$\overline{G}$$ has a vertex cover of size $$\leq n - k$$, where $$|V| = n$$.

$$CLIQUE \leq_P VERTEX-COVER$$

$$CLIQUE \leq_P INDSET$$

$$SAT$$ is $$NP$$-complete via $$a$$ where $\begin{gathered} C = Q \cup \{\#\} \cup \Gamma \\ x_{i, j, s} = true \Leftrightarrow cell[i, j] = s \\ \Phi_{start} = x_{1, 1, \#} \land x_{1, 2, q_{start}} \land x_{1, 3, w_1} \land \dots \\ \land x_{1, n^k-1, \text{\textvisiblespace}} \land x_{1, n^k, \#} \\ \Phi_{cell} = \bigwedge\limits_{i, j = 1}^{n^k} \left(\bigvee\limits_{s \in C} x_{i, j, s} \land \right. \\ \left. \bigwedge\limits_{s, t \in C, 1 \leq i, j \leq n^k} \lnot (x_{i, j, s} \land x_{i, j, t})\right) \\ \Phi_{moves} = \bigwedge\limits_{i, j \geq n^k} \text{(window}[i, j] \text{ is valid)} \\ \Phi_{accept} = \bigvee\limits_{1 \leq i, j \leq n^k} x_{i, j, q_{accept}} \end{gathered}$

$$coNP = \{\text{language } L : \overline{L} \in NP\}$$, i.e. languages for which it is easy to verify non-membership. Machine model for $$L \in coNP$$ is when $$x \in L$$, all leaves are accepting configurations; otherwise, when $$x \notin L$$, there exists one leaf which is a rejecting configuration.

$$coNP$$-complete $$= \{\text{language } B : B \in coNP, \forall A \in coNP, A \leq_P B\}$$.

$$NOSAT$$ is $$coNP$$-complete.

$$L \in NP$$-complete iff $$\overline{L} \in coNP$$-complete.

# Probabilistic Turing Machines

$$RP$$, or randomized polynomial time, are the languages $$L$$ for which there is a probabilistic Turing machine that, on input $$x$$, runs in poly($$|x|$$) and when $$x \in L$$, Pr[reaching accept] $$\geq \frac{1}{2}$$; otherwise, when $$x \notin L$$, Pr[reaching reject] $$= 1$$.

Second definition for $$RP$$: it contains languages $$L$$ for which there exists a deterministic polytime Turing machine $$V$$ such that when $$x \in L$$, for at least half of all $$y$$ with $$|y| \leq \text{poly}(|x|), V$$ accepts $$(x, y)$$; when $$x \notin L$$, for all $$y$$ with $$|y| \leq \text{poly}(|x|), V$$ rejects $$(x, y)$$.

Contrast with $$NP$$, where $$\forall x \in L$$, Pr[reaching accept] $$> 0$$, $$\forall x \notin L$$, Pr[reaching reject] $$= 1$$.

$$RP \subseteq NP$$

$$coRP$$: $$\forall x \in L$$, Pr[reaching accept] $$= 1$$, $$\forall x \notin L$$, Pr[reaching reject] $$\geq \frac{1}{2}$$.

$$coNP$$: $$\forall x \in L$$, Pr[reaching accept] $$= 1$$, $$\forall x \notin L$$, Pr[reaching reject] $$> 0$$.

$$BPP$$, or bounded error probabilistic polynomial time: $$\forall x \in L$$, Pr[reaching accept] $$\geq \frac{2}{3}$$, $$\forall x \notin L$$, Pr[reaching reject] $$\geq \frac{2}{3}$$.

$$RP \subseteq BPP$$

$$coRP \subseteq BPP$$

$$RP(\frac{1}{2}) = RP(\frac{3}{4})$$ (proof via amplification)

$$RP$$ is closed under composition.

# Communication Complexity

Model:

• Finite sets $$X, Y, Z$$

• Function $$f : X \times Y \rightarrow Z$$

• Two player, Alice and Bob

• Decide on a communication protocol beforehand

• Alice has $$x \in X$$, Bob has $$y \in Y$$

• Goal: collaboratively compute $$f(x, y)$$ by sending bits back and forth (must end with both side knowing $$f(x, y)$$)

The trivial prototol:

• Alice sends $$x$$ to Bob ($$\log |X|$$)

• Bob computes and sends $$z = f(x, y)$$ to Alice ($$\log |Z|$$)

Total: $$\log |X| + \log |Z|$$ or $$\log |Y| + \log |Z|$$

A communication protocol is a binary tree where each node is labelled by either $$a_v : X \rightarrow \{L, R\}$$ or $$b_v : Y \rightarrow \{L, R\}$$ and each leaf is labelled by an element of $$Z$$. The depth of the protocol tree is the maximum number of bits sent by the protocol.

The deterministic communication complexity of a function $$f$$ is \begin{aligned} D(f) & = \min\limits_{\text{tree for } f} \left(\max\limits_{(x, y)}(\text{number of bits}) \right) \\ & = \min\limits_{\text{tree for } f} (\text{depth of tree})\end{aligned}

$$D(EQ_n) \leq n + 1$$

A rectangle in $$X \times Y$$ is a set of the form $$R = A \times B$$ where $$A \subseteq X$$ and $$B \subseteq Y$$. $$R$$ is a rectangle iff $$(x, y) \in R \land (x', y') \in R \Leftrightarrow (x, y') \in R \land (x', y) \in R$$

Let $$T$$ be a protocol tree, $$R_v$$ be the set of inputs that causes the protocol to arrive at node $$v$$. Then $$R_v$$ is a rectangle.

A rectangle is called $$f$$-monochromatic if $$f(x, y)$$ is the same for all $$(x, y) \in R$$.

Let $$R_i \subset X \times Y$$ be a rectangle for $$i = 1, \dots, k$$. The set $$\mathcal{R} = \{R_1, \dots, R_k\}$$ is called an $$f$$-monochromatic partition (into rectangles) if each $$R_i$$ is $$f$$-monochromatic, and each $$(x, y) \in X \times Y$$ is contained in exactly one $$R_i$$.

$$C^{\text{partition}}(f) = \min \{|\mathcal{R}| : \mathcal{R} \text{ is an }f\text{-monochromatic partition}\}$$

For any protocol tree $$T$$, the rectangles $$\{R : v \text{ is a leaf in } T\}$$ are an $$f$$-monochromatic partition.

$$C^{\text{partition}}(f) \leq \min\limits_{\text{protocol tree } T} |\text{number of leaves in } T|$$

$$D(f) \geq \left \lceil \log_2 C^{\text{partition}}(f) \right \rceil$$

A fooling set $$S \subseteq X \times Y$$ is a set where all points $$(x, y) \in S$$ have the same value $$f(x, y) = z$$, and for any distinct points $$(x, y)$$ and $$(x', y')$$ in $$S$$, either $$f(x, y') \neq z$$ or $$f(x', y) \neq z$$.

$$C^{\text{partition}}(f) \geq |S| + 1$$, where $$S$$ is a fooling set for $$f$$

$$D(f) \geq \left \lceil \log_2(|S| + 1) \right \rceil$$, where $$S$$ is a fooling set for $$f$$

$$D(EQ_n) = D(GTE_n) = D(DISJ_n) = n + 1$$

Model for non-deterministic communication complexity:

• Function $$f : X \times Y \rightarrow Z$$ is known to all

• Bob does not know $$x$$, Alice does not know $$y$$

• Alice and Bob do not communicate

• Piere tries to force Alice and Bob to accept by sending certificate $$z$$. How short can $$z$$ be?

$$N(f) = \min\limits_{nondet protocol}(\text{length of cert})$$. Or, $$N(f) = \min\{k\}$$ such that there exist $$A$$ and $$B$$, for all $$x \in X$$, $$y \in Y$$, $$f(x, y) = 1 \Rightarrow \exists z \in \{0, 1\}^k, A(x, z) = 1 \land B(y, z) = 1$$, $$f(x, y) = 0 \Rightarrow \forall z \in \{0, 1\}^k, A(x, z) = 0 \lor B(y, z) = 0$$.

$$N(\lnot DISJ_n) \leq \log n$$

For all $$f$$, $$D(f) = D(\lnot f)$$.

$$N(\lnot EQ_n) \leq \log(n) + 1$$

Let $$S$$ be a fooling set where $$f(x, y) = 1$$ for all $$(x, y) \in S$$. Then $$N(f) \geq \left \lceil \log_2(|S|) \right \rceil$$.

$$N(EQ_n) \geq n$$

The set $$\mathcal{R} = \{R_1, \dots, R_k\}$$ is a cover of the $$1$$-entries (by rectangles) if (1) each $$R_i$$ is a rectangle containing only $$1$$s, and (2) every $$(x, y) \in X \times Y$$ with $$f(x, y) = 1$$ is contained in at least one $$R_i$$.

$$C^{1\text{-cover}}(f) = \min \{|\mathcal{R}| : \mathcal{R} \text{ is a cover of the } 1\text{-entries}\}$$

$$C^{0\text{-cover}}(f) = C^{1\text{-cover}}(\lnot f)$$.

$$C^{\text{partition}}(f) = C^{1\text{-cover}}(f) + C^{0\text{-cover}}(f)$$.

$$N(f) = \left \lceil \log_2(C^{1\text{-cover}}(f) ) \right \rceil$$

$$D(f) \geq N(f)$$

$$D(\lnot f) = N(f)$$

Let $$f : X \times Y \rightarrow \{0, 1\}$$ be arbitrary, $$C_0$$ be a cover of the $$0$$-entries, and $$C_1$$ be a cover of the $$1$$-entries. Then $$D(f) = O(\log C_0 * \log C_1)$$.

$$D(f) = O(N(f) * N(\lnot f))$$