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)$.