C(B, 3) PC(n, 5)

$\newcommand{\cF}{\mathcal{F}}$ $\newcommand{\eps}{\varepsilon}$ $\newcommand{\supp}{\mathrm{supp}}$ $\newcommand{\cV}{\mathcal{V}}$ $\DeclareMathOperator{\E}{\mathbb{E}}$ **Notation**: $\cF_A, \cF_B$: sets of functions. With superscripts, they will denote sets of functions consistent with certain conditions. $F_A, F_B$: random variables for functions drawn uniformly from $\cF_A, \cF_B$, or their conditioned versions. The domain will be evident from superscripts/subscripts. $V_i$ is the random variable denoting the vertex found by following the pointer from $v_0$ for $i$ steps. $\cV_i$ is the vertex set for $V_i$. Note: We use the same (permutation) function $f_A$ on $\cV_2 \rightarrow \cV_3$, and $\cV_4 \rightarrow \cV_5$. Similarly for $f_B$. That is, functions in all Alice's layers are the same, and all Bob's layers are the same. ## Theorem $C^{(B, 3)} (\mathrm{PERM\text{-}PC}(n, 5)) = \Omega(n \log n)$ ## Proof Let $\Pi= (M_1, M_2, M_3)$ be a 3-round deterministic communication protocol where at most $\varepsilon n \log n$ bits are exchanged per message, for a small enough constant $\varepsilon$ (say, $\eps= 0.01$). We identify a specific sub-rectangle $R^*$ of $\Pi$ where it should err. More precisely, we identify a sub-rectangle $R^*$ of the protocol after $M_2$, and a function $f_B$, for which the final output $V_5$ has positive entropy, so Bob cannot determine the answer (which he should know with certainty after $M_2$). Alice holds $f_A$, which goes between $\cV_i \rightarrow \cV_{i+1}$, for $i$ being even, and Bob holds $f_B: \cV_i \rightarrow \cV_{i+1}$, for $i$ being odd. All entropies are measured with respect to the uniform distribution over possible inputs (i.e. permutations on $[n]$) to the two players. We proceed to find the subrectangle $R^*$ round-by-round, by fixing $M_1,V_1, M_2$ satisfying certain conditions. ### Initial condition (no messages passed): - $H[F_A] = H[F_B] = \log n! = n \log n - O(n)$, - $H[V_i] = \log n$, for all $1 \leq i \leq 5$ --- ### Round 1: (Fixing $M_1$) : Since $|M_1|\leq \eps n \log n$, there exists $M_1 = m_1$ from Bob to Alice such that: $$H[F_B^{m_1}] := H[F_B \mid M_1 = m_1] \geq (1 - \varepsilon) n \log n$$ By subadditivity, there further exists some $V_1 = v_1^*$ such that: $$H[F_B^{m_1}(v_1^*)] \geq (1 - \varepsilon) \log n$$ (Fixing $V_1$:) Fix $V_1 = v_1^*$, and consider the subrectangle so formed. This reduces the entropy of $F_A$ by $\log n$. At this point, we know that $|\supp(V_2)| \geq n^{1-\eps}$. We would now like to say that there are *many* potential $v_2$'s for which $H[F_B^{m_1}|V_2 = v_2]$ is still large. **By [PRV] Lemma 3.2**: Given $H[F_B^{m_1}] \geq (1 - \varepsilon) n \log n$ and $H[V_2] \geq (1 - \varepsilon) \log n$, there are at least $\ell = n^{1 - 2\varepsilon}$ vertices $a_1, \ldots, a_\ell \in |\supp(V_2)|$ such that: $$H[F_B^{m_1} \mid V_2 = a_j] \geq (1 - 2\varepsilon) n \log n$$ Let $A_2 := \{ a_1, \ldots, a_\ell \}$ and let $\cF_{B, a_j} := \cF_B^{m_1} \mid V_2 = a_j$. Remark: The correlation induced between the possible functions between layers $\cV_1, \cV_2$, and $\cV_3, \cV_4$ due to Bob's message $m_1$ necessiates the above definition. --- ### Round 2: We now consider what happens when Alice sends $M_2$. Without loss of generality, we may take that $M_2 = M_{21} \; \Vert \; M_{22} \; \Vert \; M_{23}$ to Bob, where $M_{21}$ is an arbitrary message, $M_{22}$ is a fixed message revealing $V_1$ (which is $v_1^*$ in our current rectangle), and $M_{23}$ contains $f_A(v_2)$ for every possible $v_2 \in \supp(V_2)$. -- Possibly rephrase this in terms of considering the subrectangle that fixes $f_A(v_2)$ Our goal is to find a specific $M_2=m_2$ that satisfies the following: a. Fixes values $f_A(v)$ for all $v\in A_2$ b. $|\supp(V_4)| > 0.6n$ in the resulting subrectangle after fixing $M_2$. c. $H[F_A^{m_2}] \geq (1-4\eps) n \log n$ We show that a *random* assignment for $A_2$ from the set of possible assignments satisfies all three conditions with constant probability. It may be useful to think of Condition (b) as the following: $i\in \supp(V_4)$, if there is a "path" from some $a_j \in A_2$ to it under the (fixed) assignment $\sigma$ and over choices of $f_B \in \cF_{B, a_j}$. This motivates the following definitions for cases when an $i \in \cV_4$ potentially has many paths to it: #### Definitions: - A vertex $i \in V_4$ is **locally good** with respect to $a_j \in V_2$ if: $$ |\mathcal{F}_{B, a_j}^{-1}(i) | \geq n^{1 - 8\varepsilon} $$ - A vertex $i \in V_4$ is **globally good** if it is locally good for at least $\frac{l}{4}$ different $a_j$'s (with $l = n^{1 - 2\varepsilon}$) --- #### Claim 1 Each $a_j \in A_2$ has at least $\frac{3n}{4}$ locally good vertices $i \in V_4$. **Proof**: $H[F_{B, a_j}] \geq (1 - 2\varepsilon) n \log n$ implies $I[F_{B, a_j}^{-1}] \leq 2 \varepsilon n \log n$. By subadditivity of entropy and Markov's inequality, for at least a $\frac{3}{4}$ fraction of the vertices $i \in V_4$, we have: $$ I[F_{B, a_j}^{-1}(i)] \leq 8\varepsilon \log n. $$ $$ H[F_{B, a_j}^{-1}(i)] \geq (1 - 8\varepsilon) \log n. $$ $$ |\mathcal{F}_{B, a_j}^{-1}(i)| \geq n^{1 - 8\varepsilon}. $$ Therefore, each $a_j$ has at least $\frac{3n}{4}$ *locally good* vertices $i \in V_4$ for which the preimage under $\mathcal{F}_{B, a_j}^{-1}$ has large support. --- #### Claim 2: The number of globally good $i \in V_4$ is at least $\frac{2n}{3}$ **Proof**: Each $a_j$ has $\geq \frac{3n}{4}$ locally good $i$'s from Claim 1. Let there be $s$ globally good $i$'s. Then: $$s \cdot l + (n - s) \cdot \frac{l}{4} \geq l \cdot \frac{3n}{4} \Rightarrow s \geq \frac{2n}{3}$$ --- #### Claim 3: -- The analysis is easier for a_1, \ldots, a_\ell being independently assigned. Let $\{a_1, \ldots, a_l\} \subseteq \cV_2$ be a set of $l = n^{1 - 2\varepsilon}$ vertices, of which at least an $\alpha = \frac{l}{4}$ fraction are *good* for a fixed globally good vertex $i \in V_4$. That is, for each good $a_j$, we have: $$ |\mathcal{F}_{B, a_j}^{-1}(i)| \geq n^{1 - 8\varepsilon}. $$ Let $\sigma: A_2 \rightarrow \cV_3$ be a randomly chosen value for $f_A(a)$, for each $a\in A_2$ (with no collisions) Then, the probability (over choice of $\sigma$) that $i \notin \supp(V_4)$ is: $$\Pr_\sigma [\forall a_j \in A_2 :~~ i \notin \cF_{B,a_j}(\sigma(a_j))] ~ \leq~ \exp\left(-n^{1 - 16\varepsilon}\right)$$  <details><summary> Proof considering all assignments independent </summary> For a globally good $i$: \begin{align*} \Pr[\bigwedge_{j \in [\ell]} \sigma(a_j) \notin \cF_{B,a_j}^{-1}(i)] &\leq \prod_{j \in [\ell]} \left(1-\frac{|\cF_{B,a_j}^{-1}(i)|}{n}\right) \\ & \leq (1-n^{-8\eps})^{\ell/4} \qquad \ldots \textrm{since i is globally good} \\ & \leq \exp(-n^{(1-10\eps)}) \end{align*} </details> <details open><summary> Proof (considering dependencies) Needs to be updated for some notation (Click to expand) </summary> **Proof**: Let, wlog, $a_1, a_2, \ldots, a_{\ell/4}$ be good for $i$. For a fixed $i$, we can view the random choice of assignments to $A_2$ under $F_A$ as follows: $\sigma(a_1)$ is randomly chosen from $[n]$ $\sigma(a_2)$ is randomly chosen from $[n]-\{\sigma(a_1)\}$ ... $\sigma(a_j)$ is randomly chosen from $[n] - \{\sigma(a_1), \sigma(a_2), \ldots, \sigma(a_{j-1})\}$ Let $\mathcal{E_j}$ be the event that $\sigma(a_j) \notin \cF_{B,a_j}^{-1}(i)$ We then have: $$\Pr[\mathcal{E_j} | \bigwedge_{r<j} \mathcal{E_r}] \leq \left(1-\frac{|\cF_{B,a_j}^{-1}(i)|-(j-1)}{n- (j-1)}\right)$$ For $j\leq n^{1-8\eps}/4$, the above is at most $1-\frac{3n^{1-8\eps}}{4n}$ . Let $\ell' := \lfloor n^{1-8\eps}/4\rfloor$. We have: \begin{align*} \Pr[\bigwedge_{j=1}^\ell \mathcal{E}_j] &\leq \Pr[\bigwedge_{j=1}^{\ell'} \mathcal{E}_j] \\ & \leq ~ \left(1-\frac{3n^{1-8\eps}}{4n}\right)^{\ell'} \\ & \leq \exp( -3n^{1-16\eps}/4) \end{align*} </details> --- --- Let $Z$ be a random variable (determined by $\sigma$) denoting the number of globally good $i$'s in $\supp(V_4)$. From Claim 2 and Claim 3, $$ \mathbb{E}_{\sigma} \left[Z \right] \geq \frac{2n}{3} \cdot \left(1 - \exp\left(-{n^{1 - 16\varepsilon}}\right)\right) > 0.6 n, $$ Therefore, there exists a fixing of values for $f_A$ on $A_2$, corresponding to some $\sigma = \sigma^*$ such that $|\supp(V_4)| >0.6n$. **Fixing $M_2$:** Consider messages $M_2$ with $M_{23} = m_{23}$, which matches $\sigma^*$ on $A_2$. This satisfies Conditions (a) and (b) required on $M_2$ as given. Since $M_2$ which consists at most $\varepsilon n \log n$ bits $M_{21}$, $\log n$ bits $M_{22}$ due to $V_1 = v_1^*$, and $m_{23}$, we have: $$ H[F_A \mid M_2] \geq ((1 - \eps)n - n^{1 - 2\eps}) \log n \geq (1-1.01 \cdot\eps)n \log n$$ Fix an $M_2 = m_2$, such that $H[F_A|M_2 = m_2] \geq (1-1.01 \cdot\eps)n \log n$. We thus have satisfied condition \(c) as well. This concludes the choice of $M_2$. **Finishing the argument**: Consider the subrectangle $R^*$ formed by the choice of $m_1, m_2$ as given above. By averaging, there is a subset $S_4 \subseteq \cV_4$ of $0.4n$ vertices such that: $H[F_A^{m_2}(i)] > \frac{1}{2} \log n$. Call these the "uncertain vertices", since Bob cannot determine $f_A(i)$ on these vertices. Since $|\supp(V_4) \cap S_4|>0$, there is some function $f_B^*$ such that $V_4$ is an uncertain vertex for Bob. This should not happen if Bob has to determine $v_5$ with certainty. This concludes the proof. ---