  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 Erd\H{o}s and Simonovits) for $u=v$ and shown true
under the restriction $m_t\ge e^{-4t}$. Moreover we prove that for any
$\epsilon>0$, 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> 0, \exists \delta> 0$ such that $\forall S,u,v$ \begin{equation*}
\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,
\end{equation*} 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)$.

Computational Complexity;Probability