Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences

Let u, v ∈ R
₊
^Ω
be positive unit vectors and S ∈ R
₊
^Ω×Ω
be a symmetric substochastic matrix. For an integer t ≥ 0, let m
_t
= 〈 v, S
^t
u〉, 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
≥ 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
≥ e
^-4t
. Moreover we prove that for any ε>0, a stronger inequality m
_t+2
≥ t
^1-ε
· m
_t
^1+2/t
holds unless m
_t+2
m
_t-2
≥ δm
_t
²
for some δ that depends on ε only. Phrased differently, ∀ε > 0, ∃δ > 0 such that ∀S, u, v m
_t+2
/m
_t
^1+2/t
≥ min{t
^1-ε
, δm
_t
^1-2/t
/m
_t-2
}, ∀t ≥ 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 Ω(klog k). queries and the randomized communication complexity of the k-Hamming distance problem is Ω(k log k). Further we show that any randomized parity decision tree computing k-Hamming weight has size exp(Ω(k log k)).