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 Erd?s and Simonovits) for u = v and shown true under the restriction m t e ? 4 t . Moreover we prove that for any 0" 0 , a stronger inequality m t +2 t 1 ? m t 1+2 t holds unless m t +2 m t ? 2 m t 2 for some that depends on only. Phrased differently, 0, exists delta 0" 0 0 such that S u v m t +2 m t 1+2 t min t 1 ? m t ? 2 m t 1 ? 2 t 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 ( k log 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 ) .