Computer Science/Discrete Mathematics Seminar II

In the previous talk, we defined Subgroup Tests and the interactive proof system induced by them. In addition, we showed that if the Aldous--Lyons conjecture was true, then this interactive proof system contains only decidable languages. In this talk, we describe why the Halting Problem can be decided in our interactive proof system, which in turn refutes the Aldous--Lyons conjecture. This is done in two steps: The first relates Subgroup Test to a new subclass of non-local games which we term Tailored Games. The second shows that the techniques of MIP*=RE can be refined so that all the games in it are tailored, or in acronym fashion, that Tailored-MIP*=RE.

This talk is based on a joint work with Lewis Bowen, Alex Lubotzky and Thomas Vidick.