|Computer Science/Discrete Mathematics Seminar I|
|Topic:||Near log-convexity of measured heat in (discrete) time and consequences|
|Affiliation:||University of Washington|
|Date:||Monday, March 11|
|Time/Room:||11:00am - 12:00pm/Simonyi Hall 101|
We answer a 1982 conjecture of Erdő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)$.