A common theme in mathematics is that limits of finite objects are well behaved. This allows one to prove many theorems about finitely approximable objects, while leaving the general case open --- examples for this are Gottschalk's conjecture, Kaplansky's direct finiteness conjecture, and many more. When the topology of the space is somewhat coarse, it becomes very hard to decide whether every object is approximable by finite ones, or whether there exist non-approximable objects. Some of the more famous problems in various fields of mathematics can be framed this way; this includes Connes' embedding problem (CEP) in functional analysis, the Aldous--Lyons conjecture in probability theory, the soficity problem of Gromov--Weiss in group theory, and more. 

In 2019, Ji--Natarajan--Vidick--Wright--Yuen resolved CEP in the negative, namely, they showed that there are non-approximable characters of the free group. The amazing thing about their result is that it is deduced from complexity theory, and specifically from undecidability in certain (quantum) interactive proof systems. Inspired by their work, we suggest a novel interactive proof system which is related to the Aldous--Lyons conjecture in the following way: If the Aldous--Lyons conjecture was true, then every language in this interactive proof system is decidable. A key concept we introduce for this purpose is that of a Subgroup Test, which is our analogue of a Non-local Game. By providing a reduction from the Halting Problem to this new proof system, we refute the Aldous-Lyons conjecture.

In this first talk we introduce the main concepts, motivate the conjecture and give a high level description of the proof strategy. No special mathematical background will be assumed.

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

A common theme in mathematics is that limits of finite objects are well behaved. This allows one to prove many theorems about finitely approximable objects, while leaving the general case open — examples for this are Gottschalk's conjecture, Kaplansky's direct finiteness conjecture, and many more. When the topology of the space is somewhat coarse, it becomes very hard to decide whether every object is approximable by finite ones, or whether there exist non-approximable objects. Some of the more famous problems in various fields of mathematics can be framed this way; this includes Connes' embedding problem (CEP) in functional analysis, the Aldous–Lyons conjecture in probability theory, the soficity problem of Gromov–Weiss in group theory, and more. 

In 2019, Ji–Natarajan–Vidick–Wright–Yuen resolved CEP in the negative, namely, they showed that there are non-approximable characters of the free group. The amazing thing about their result is that it is deduced from complexity theory, and specifically from undecidability in certain (quantum) interactive proof systems. Inspired by their work, we suggest a novel interactive proof system which is related to the Aldous--Lyons conjecture in the following way: If the Aldous–Lyons conjecture was true, then every language in this interactive proof system is decidable. A key concept we introduce for this purpose is that of a Subgroup Test, which is our analogue of a Non-local Game. By providing a reduction from the Halting Problem to this new proof system, we refute the Aldous-Lyons conjecture.

In this first talk we introduce the main concepts, motivate the conjecture and give a high level description of the proof strategy. No special mathematical background will be assumed.

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

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.

The growing success of machine learning across a wide range of domains and applications has made it appealing to be used also as a tool for informing decisions about humans. But humans are not your conventional input: they have goals, beliefs, and aspirations, and take action to promote their own self-interests. Given that standard learning methods are not designed to handle inputs that "behave", it is natural to ask: how should we design learning systems when we know they will be deployed and used in social environments?

As a starting point, I will present the problem of strategic classification, in which users can modify their features (at a cost) in response to a learned classifier in order to obtain favorable predictions. I will then describe some of our work in this field, demonstrating how even mild forms of strategic behavior can dramatically transform the learning problem, and the role game theory can play in addressing some of the new challenges that arise. Finally, I will argue for strategic classification as a framework that can be useful for formally reasoning about learning under user behavior in general, and which holds potential for weaving more elaborate forms of economic modeling into the learning pipeline.