MIAO talk by Morgan Shirley

Tuesday, September 17, 2024, Morgan Shirley, postdoc at the University of Victoria, Canada, will give a talk on "Large corner-free sets in high dimensions".

Abstract:
A central question in additive combinatorics is to understand how large arithmetic progression-free sets can be. In this talk, I will focus on this question for high-dimensional generalization of arithmetic progressions (AP) known as corners. A (2-dimensional) corner is a triple of the form (x,y),(x+d,y),(x,y+d) for some d > 0 in [N]x[N]. Extending this definition to higher dimensions, a k-dimensional corner in [N]^k is a (k+1)-tuple defined similarly for some d. While it is known that corner-free sets have a vanishingly small density, the precise bounds on their size remain unknown.
Until recently, the best-known corner-free sets were derived from constructions of AP-free sets: a construction of a 3-term AP-free set by Behrend from 1946, and a generalization by Rankin for k-term APs in 1961. New results by Linial and Shraibman (CCC 2021) and Green (New Zealand Journal of Mathematics 2021) changed this picture; they improved the upper bound for k=2 by adopting a communication complexity point of view.
Morgan will discuss the recent work where the same perspective of communication complexity has been employed and obtain the first improvement on the upper bound of the size of high-dimensional (k > 2) corner-free sets since the original construction of Rankin.

Based on joint work with Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, and Adi Shraibman.

Bio:
Morgan Shirley is a researcher in the field of theoretical computer science. This Autumn Morgan will be starting as a postdoc at the University of Victoria, hosted by Sajin Koroth and Bruce Kapron. Morgan received a PhD from the University of Toronto under the supervision of Toni Pitassi and also has a M.S. degree from Oregon State University, advised by Mike Rosulek, working on problems in cryptographic complexity.

More recently, Morgan has focused on computational complexity and is most excited about questions related to communication complexity, proof complexity, and connections between theoretical computer science and additive combinatorics.

Host:
Susanna de Rezende, MIAO