Logic Seminar

We study the complexity of locally checkable labeling problems on Borel graphs induced by actions of Z^n. Our results separate various complexity classes that were not previously known to be distinct and provide counterexamples to a number of natural conjectures in the field. In particular, we discuss a problem that has a factor-of-i.i.d. solution but no finitary factor-of-i.i.d. solution. We also expl as a cain how this problem servesounterexample to the shift being universal in the Baire measurable setting: it has a solution mod meager on the shift action, but not on all actions. This is joint work with Bernshteyn, Lyons, and Weilacher.