[iasmath-semru] Stability and Testability Seminar

[Anthony V. Pulido]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540

The following message comes from Alexander Luboztky, 
alex.lubotzky at mail.huji.ac.il

-------------

Dear All,

     I plan to run a weekly seminar at the IAS, Princeton on "Stability 
and Testability".  Stability (in group theory) deals with questions of 
the following type: given a map f from a group G to a group H which 
behaves like a homomorphism, is it really close to a homomorphism? 
Testability is a topic in computer science (a.k.a. Property Testing) 
dealing  with studying whether a property can be checked by sampling 
only a small number of random inputs.

     These two subjects are not only connected with each other, but over 
the last few years found relations to  other mathematical and CS areas 
like: expanders, high dimensional expanders, cohomology, C*-algebras, 
error correcting codes, quantum computation and more.

    The seminar is aimed toward participants with very varied 
backgrounds so all speakers have been (and will be) asked to make their 
talks available to a wide audience.

    The seminar will meet on Wednesdays 11:00 AM- 12:15 PM  Princeton 
time starting on Oct. 14, 2020.

    On Oct. 12, 2020,  14:00 PM, I will give a talk at the IAS as part 
of the members seminar which is also related to this seminar.


    Here is the plan for the first five talks:

Oct. 14 , Alex Lubotky (Hebrew University & IAS)
  Title:   Introduction to stability and testability
Abstract: The talk will be an introduction and a road map to the various 
connections the topic has with other areas of math and CS.

Oct. 21 , Jonathan Mosheiff (CS, Carnegie Mellon)
  Title: Stability and testability - a computational perspective
*                  Abstract: *In this talk we survey the recent 
connection (a joint work with Becker and Lubotzky) between certain group 
theoretic notions related to stability, and a novel class of problems 
from the realm of /property testing/.
Consider the computational problem where we are given a tuple of 
permutations in Sym(n), and wish to determine whether these permutations 
satisfy a certain system of equations E. We say that E is /testable/ if 
there is an algorithm (called a /tester/) that queries only a constant 
number of entries of the given permutations, and probabilistically 
distinguishes between the case where the permutations satisfy E, and the 
case in which they are epsilon-far from any tuple of permutations 
satisfying E. Note that in our definition of this problem we depart from 
the more classical setting of property testing, where the object to be 
tested is either a function or a graph.
We observe an intriguing connection between the group presented by E, 
which we denote G, and the above computational problem. It turns out 
that G is stable if and only if a certain natural algorithm is a tester 
for E. Thus, established results about the stability of certain groups 
yield testers for corresponding systems of equations. Further exploring 
this connection, we discover that the testability of E can be fully 
characterized in terms of the group G. Studying this characterization 
yields both positive and negative results. For example, amenability of G 
implies that E is testable. On the other hand, if G has property (T) and 
finite quotients of unbounded cardinality, then E is not testable.
We conclude by presenting some natural open questions motivated by this 
work.

Oct. 28,  Oren Beker ( Cambridge U. )
                Title:Stability, testability and property (T)
                Abstract : We show that if G=<S|E> is a discrete group 
with Property (T) then E, as a system of equations over S, is not stable 
(under a mild condition). That is, E has approximate solutions in 
symmetric groups Sym(n), n>=1, that are far from every solution in 
Sym(n) under the normalized Hamming metric.
The same is true when Sym(n) is replaced by the unitary group U(n) with 
the normalized Hilbert--Schmidt metric.
We will recall the relevant terminology, sketch the proof in a special 
case, and extend the instability result to show non-testability.
The discussion will lead us naturally to a slightly weaker form of 
stability, called flexible stability, and we will survey its recent study.
Based on joint works with Alex Lubotzky and Jonathan Mosehiff


Nov. 4,   Adrian Ioana (UCSD)
Title: Stability and sofic approximations for product groups and 
property (tau).
  Abstract: A countable group G is called sofic if it admits a sofic 
approximation: a sequence of asymptotically free almost actions on 
finite sets. Given a sofic group G, it is a natural problem to try to 
classify all its sofic approximations and, more generally, its 
asymptotic homomorphisms to finite symmetric groups. Ideally, one would 
aim to show that any almost homomorphism from G to a finite symmetric 
group is close to an actual homomorphism. If this is the case, then G is 
called stable in permutations, or P-stable. In this  talk, I will first 
present a result providing a large class of product groups are not 
P-stable. In particular, the direct products of the free group on two 
generators with itself and with the group of integers are not P-stable. 
This implies that P-stability is not closed under the direct product 
construction, which answers a question of Becker, Lubotzky and Thom.  I 
will also present a more recent result, which strengthens the above in 
the case when G is the direct product of the free group on two 
generators with itself. This shows, answering a question of Bowen, that 
G admits a sofic approximation which is not essentially a “branched 
cover” of a sofic approximation by homomorphisms.

  Nov. 11, Peter Burton ( U. of Texas)
Title: Flexible stability and nonsoficity
                 Abstract: A sofic approximation to a countable discrete 
group is a sequence of finite models for the group that generalizes the 
concept of a Folner sequence witnessing amenability of a group and the 
concept of a sequence of quotients witnessing residual finiteness of a 
group. If a group admits a sofic approximation it is called sofic.
It is a well known open problem to determine if every group is sofic. A 
sofic group G is said to be flexibly stable if every sofic approximation 
to G can converted to a sequence of disjoint unions of Schreier graphs 
on coset spaces of G by modifying an asymptotically vanishing proportion 
of edges. We will discuss a joint result with Lewis Bowen that if 
\mathrm{PSL}_d(\mathbb{Z}) is flexibly stable for some d \geq 5 then 
there exists a group which is not sofic.



If you are interested to get regular e-mails about the seminar, please 
let me know.  Yours,  Alex Lubotzky (alex.lubotzky at mail.huji.ac.il)


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/iasmathsemrutgers/attachments/20201002/4e2ce881/attachment.html>