Eric Blais says: That paper looks fantastic! And I do not use the word lightly. Theorem 1.8, the main communication complexity result that gives an optimal bound on the communication complexity of the k-Hamming distance problem, resolves what was one of my favourite open problems. (Both for the applications to property testing and because it is such a natural and fundamental problem.) I have spent quite a bit of effort trying to prove it myself, and from what I understand at the moment, the proof obtained in this manuscript uses a completely different approach than the one(s) I had been following and that I thought would eventually be used to prove the theorem. The route itself does look rather novel and intriguing; I will be studying it with lots of interest and I look forward to seeing whether/how it will be used to prove other lower bounds in the future as well.
Let $u,v \in \mathbb{R}^\Omega_+$ be positive unit vectors and $S\in\mathbb{R}^{\Omega\times\Omega}_+$ be a symmetric substochastic matrix. For an integer $t\ge 0$, let $m_t = \smash{\left\langle v,S^tu\right\rangle}$, which we view as the heat measured by $v$ after an initial heat configuration $u$ is let to diffuse for $t$ time steps according to $S$. Since $S$ is entropy improving, one may intuit that $m_t$ should not change too rapidly over time. We give the following formalizations of this intuition.
We prove that $m_{t+2} \ge m_t^{1+2/t}\!,$ an inequality studied earlier
by Blakley and Dixon (also Erdos and Simonovits) for $u=v$ and shown true
under the restriction $m_t\ge e^{-4t}$. Moreover we prove that for any
$\epsilon\gt0$, a stronger inequality
$m_{t+2} \ge t^{1-\epsilon}\cdot \smash{m_t^{1+2/t}}$
holds unless $m_{t+2}m_{t-2}\ge \delta m_t^2$ for some
$\delta$ that depends on $\epsilon$ only.
Phrased differently, $\forall \epsilon\gt 0, \exists \delta\gt 0$
such that $\forall S,u,v$
$$ \frac{m_{t+2}}{m_{t}^{1+2/t}}\ge
\min\left\{t^{1-\epsilon}, \delta\frac{m_t^{1-2/t}}{m_{t-2}}\right\},
\quad \forall t \ge 2,$$
which can be viewed as a truncated log-convexity statement.
Using this inequality, we answer two related open questions in complexity theory: Any property tester for $k$-linearity requires $\Omega(k\log k)$ queries and the randomized communication complexity of the $k$-Hamming distance problem is $\Omega(k\log k)$. Further we show that any randomized parity decision tree computing $k$-Hamming weight has size $\exp\left(\Omega(k\log k)\right)$.
See ECCC TR18-144.