Mert Saglam, UW CS

Monday, April 8, 2019 - 2:30pm to 3:30pm

MEB 238

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 even earlier by Blakley and 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 Ω(k log k) and that consequently any property tester for k-linearity requires Ω(k log k) queries.