Monotonicity Testing Lower Bounds via Communication Complexity

Prateek Kumar

Nov 9, 2018

CS5030: Communication Complexity
Class Presentation

Property Testing

Let $D$, $R$ be two sets, then preperty $\mathcal{P}$ is a set of functions from $D$ to $R$.

Examples: Linearity, Monotonicity

Property Testing: Given a black box which outputs $f(x)$ when provided with query $x$, goal is to decide whether $f \in \mathcal{P}$ using as few queries to the black box as possible.

Exact property testing requires $\Theta(|D|)$ queries. So, our focus will be on randomized algorithms.

$\epsilon$-Property Testing

Decide whether $f \in \mathcal{P}$ or $f$ is $\epsilon$-far from $\mathcal{P}$.

$f$ is $\epsilon$-far from $\mathcal{P}$ iff $\forall g \in \mathcal{P}$, $f$ and $g$ differ at $\geq \epsilon|D|$ values.

Query Complexity: $\min_{T \in \text{testers}} \max_{f : D \to R} Q(T, f)$

Testers can be adaptive or non-adaptive, have one-sided or two-sided errors.

Monotonicity testing upper bounds

Boolean case: $D = \{0, 1\}^n, R = \{0, 1\}$
$f : \{0, 1\}^n \to \{0, 1\}$ is monotone iff $f(x_0) \leq f(x_1)$ for all $x_0, x_1$ such that $x_0$ and $x_1$ differ at $i$th bit only and $x_0$ has 0 as $i$th bit and $x_1$ has 1 as the $i$th bit.

Theorem: For $\epsilon$-monotone testing (randomized), the upper bound on number of queries is $O(\frac{n}{\epsilon})$. For larger ranges, it is $O(\frac{n\log_2(|R|)}{\epsilon})$ (Proof at the end, if time available)

Monotonicity testing lower bounds

First we will see bounds for larger ranges($|R| = \Omega(n)$).

Theorem: For large enough ranges, $R$ and $\epsilon = \frac{1}{8}$ every adaptive monotonicty tester with 2-sided error uses $\Omega(n)$ queries.

Proof of the theorem

We will reduce $\text{DISJ}$ to $\frac{1}{8}$-monotonicity testing.

Let $T$ be a randomized tester to distinguish monotone and $\frac{1}{8}$-far from monotone.

We will develop a public-coin randomized protocol for $\text{DISJ}$.

Let $A, B \subseteq [n]$ and let Alice and Bob have $A$ and $B$ respectively.

Lemma: Let $A, B \subseteq [n]$, function $h_{AB} : 2^{[n]} \to \mathbb{Z}$ defined as

$$ h_{AB}(S) = 2|S| + (-1)^{|S \cap A|} + (-1)^{|S \cap B|} $$

then,

  1. $A \cap B = \phi$ implies $h$ is monotone.
  2. $A \cap B \neq \phi$ implies $h$ is $\frac{1}{8}$-far from monotone.

Let us assume the lemma is true (proof, we will see in sometime)

Protocol

Alice and Bob will agree on random bits and feed those bits to their own copies of the tester $T$.

The tester has to decide whether $h_{AB}$ is monotone or $\frac{1}{8}$-far from monotone.

The tester will query for $h_{AB}(S)$ for some $S \in \{0, 1\}^n$.

Alice and Bob will together decide the value of $h_{AB}(S)$ and feed their testers.

  1. Until $T$ halts:
    • Let $S$ be the query asked by $T$.
    • Alice sends $(-1)^{|S \cap A|}$ to Bob. (1-bit)
    • Bob sends $(-1)^{|S \cap B|}$ to Alice. (1-bit)
    • Both compute $h_{AB}(S)$ and feed their testers.
  2. If $T$ accepts $h_{AB}$ then Alice/Bob declare $\text{DISJOINT}$, else they declare $\text{NOT DISJOINT}$

Communication complexity of the protocol $= 2(\text{No. of queries asked by }T)$

Since $\text{DISJ}$ has $\Omega(n)$ public coin randomized complexity, the query complexity of monotone is $\Omega(n)$.

Proof of the lemma

Case (i) $A \cap B = \phi$

Let $S \subseteq [n] - \{i\}$.

Since $A$ and $B$ are disjoint, $i \notin $ at least one of $A$ and $B$.

$h_{AB}(S \cup \{i\}) - h_{AB}(S) \geq 0$
$\forall i \in [n], S \subseteq [n] - \{i\}$

$\therefore$ $h_{AB}$ is monotone.

Case (ii) $A \cap B \neq \phi$

Let $i \in A \cap B$.

Consider $S \subseteq [n] - \{{i\}}$ such that $(-1)^{|S \cap A|} = 1$ and $(-1)^{|S \cap B|} = 1$.

In this case,
$h_{AB}(S \cup \{i\}) - h_{AB}(S) < 0$.

There are at least $2^{n-1}/4 = 2^n/8$ possible values for $S$ for a given pair $A, B$. (Reason, next slide)

Consider sets $A’ = A - B, B’ = B - A$.

$Pr_{S}[|S \cap C| \mod 2 = 0] = \frac{1}{2}$ for any non-empty set $C \subseteq [n]$

Assuming $A’$ and $B’$ to be non-empty.

Since $A’, A \cap B, B’$ are all mutually disjoint, we have that the events $(|S \cap A’| \mod 2 = 0)$, $(|S \cap (A \cap B)| \mod 2 = 0)$, $(|S \cap B’| \mod 2 = 0)$ are all mutually independent.

$\therefore Pr_{S}((-1)^{|S \cap A|} = 1 \text{ and } (-1)^{|S \cap B|} = 1) = Pr_{S}(|S \cap A’| \mod 2 = 0$ and $|S \cap (A \cap B)| \mod 2 = 0$ and $|S \cap B’| \mod 2 = 0) + Pr_{S}(|S \cap A’| \mod 2 = 1$ and $|S \cap (A \cap B)| \mod 2 = 1$ and $|S \cap B’| \mod 2 = 1) = \frac{1}{2}*\frac{1}{2}*\frac{1}{2} + \frac{1}{2}*\frac{1}{2}*\frac{1}{2} = \frac{1}{4}$

Note: When $A’$ is empty, then both $A \cap B$ and $B’$ must have even number of elements and same probability of 14 will be obtained.

For each of the possible pair $(S, S \cup \{i\})$, we have to change one of the values of the function $h_{AB}$ (i.e. either $h_{AB}(S)$ or $h_{AB}(S \cup \{i\})$) to make it monotone.

Total no. of such modifications $\geq \frac{2^n}{8}$
$\therefore$ $h_{AB}$ is $\frac{1}{8}$-far from monotone.

Query complexity when $|R| = \Omega(\sqrt{n})$

Trick is to truncate $h_{AB}$ to obtain $h’_{AB}$ as follows:

  1. $h_{AB}(S)$ $< n - c\sqrt{n} \implies h’_{AB} = n - c\sqrt{n}$.
  2. $h_{AB}(S)$ $> n + c\sqrt{n} \implies h’_{AB} = n + c\sqrt{n}$.
  3. $h’_{AB}(S) = h_{AB}(S)$ in all other cases.

Case (i) When $A, B$ are disjoint, truncating gives another monotone function.

Case (ii) When $A, B$ are not disjoint, $h’_{AB}$ turns out to be $\frac{1}{16}$-far from monotone.
First, see that $h_{AB}$ and $h’_{AB}$ differ in at most $\frac{1}{16}$ entries (using Chebyshev’s inequlaity).
Hamming distance obeys triangle inequality. So $h’_{AB}$ is $\frac{1}{16}$-far from montone.

Query complexity when $|R| = o(\sqrt{n})$

Let $m = |R|^2$

Consider a function $g : [m] \to R$. In this case, we define $h : [n] \to R$ as $h(S) = g(S \cap [m])$

$g$ is monotone $\implies$ $h$ is monotone (Clear from def.).

Next, we will show that
$g$ is $\epsilon$-far from monotone $\implies$ $h$ is $\epsilon$-far from monotone.

Suppose $h$ is not $\epsilon$-far from monotone $\implies$ $\exists$ monotone $h’$ such that $Pr_{X \subseteq [m], Y \subseteq [n]-[m]}[h(X \cup Y) \neq h’(X \cup Y)] \leq \epsilon$.

Using averaging argument,
$\exists Y_0$ such that $Pr_{X \subseteq [m]}[h(X \cup Y_0) \neq h’(X \cup Y_0)] \leq \epsilon$

Define $g’$ as $g’(X) = h’(X \cup Y_0)$.
$\therefore Pr_{X \subseteq [m]}[g(X) \neq g’(X)] \leq \epsilon$
$\implies$ $g$ is also not $\epsilon$-far from monotone.

To test $g$, we can test $h$ and return the result.

Since $g$ requires $\Omega(m)$ queries, $h$ also requires $\Omega(m) = \Omega(|R|^2)$ queries.

Monotonicity testing upper bounds

Theorem: For $\epsilon$-monotone testing (randomized) and boolean range, the upper bound on number of queries is $O(\frac{n}{\epsilon})$. For larger ranges, it is $O(\frac{n\log_2(|R|)}{\epsilon})$.

(Proof on the board)

References

  1. Communication Complexity (for Algorithm Designers), Tim Roughgardden (Chapter 8).
  2. Property Testing Lower Bounds Via Communication Complexity, Eric Blais, Joshua Brody, Kevin Matulef (Section 4).