Near log-convexity of measured heat in (discrete) time and consequences

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

Date

Speakers

Mert Saglam

Affiliation

University of Washington