Mert Saglam, University of Washington

Abstract

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