Talks
Spring 2017

A Lower Bound for the k-colored Sum-free Problem in Z_m^n

Tuesday, June 19th, 2018 2:00 pm2:45 pm

Add to Calendar

The main result of this talk is a lower bound for the maximum size of a k-colored sum-free set in Z_m^n, where k\geq 3 and m\geq 2 are fixed and n tends to infinity. Such sets were first considered for k=3 due to their connections to fast matrix multiplication algorithms, but they can also be used to obtain bounds on the possible efficiency of property testing algorithms testing for k-cylce freeness. If m is a prime power, our lower bound matches (up to lower order terms) the previously known upper bound for the maximum size of a k-colored sum-free set Z_m^n. Our lower bound generalizes prior work of Kleinberg-Sawin-Speyer for the case k=3, in which they used a result of Pebody. In the talk, we will sketch the proof and highlight the key new ideas. Joint work with László Miklós Lovász.