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