# Near log-convexity of measured heat in (discrete) time and consequences

 Computer Science/Discrete Mathematics Seminar I Topic: Near log-convexity of measured heat in (discrete) time and consequences Speaker: Mert Sağlam Affiliation: University of Washington Date: Monday, March 11 Time/Room: 11:00am - 12:00pm/Simonyi Hall 101 Video Link: https://video.ias.edu/csdm/2019/0311-MertSaglam

We answer a 1982 conjecture of Erd&‌#337;s and Simonovits about the growth of number of $k$-walks in a graph, which incidentally was studied earlier by Blakley and Dixon in 1966. We prove this conjecture in a more general setup than the earlier treatment, furthermore, through a refinement and strengthening of this inequality, we resolve two related open questions in complexity theory: the communication complexity of the $k$-Hamming distance is $\Omega(k \log k)$ and that consequently any property tester for k-linearity requires $\Omega(k \log k)$.