Speaker: Anton Bernshteyn (UCLA)
Title. Complexity of local problems on grids
Abstract. A common theme throughout mathematics and computer science is the desire to rigorously understand how hard various problems of interest are. Depending on the subject area, different notions of complexity arise, resulting in different complexity hierarchies. In this talk I will discuss recent results that compare several such hierarchies for combinatorial coloring problems, with a particular focus on the case when the underlying graph is a square grid. This talk is based on joint work with Katalin Berlow, Clark Lyons, and Felix Weilacher.