<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body>
<p><font face="Helvetica, Arial, sans-serif">INSTITUTE FOR ADVANCED
STUDY<br>
School of Mathematics<br>
Princeton, NJ 08540<br>
<br>
The following message comes from Alexander Luboztky,
<a class="moz-txt-link-abbreviated" href="mailto:alex.lubotzky@mail.huji.ac.il">alex.lubotzky@mail.huji.ac.il</a><br>
<br>
-------------</font></p>
<font face="Helvetica, Arial, sans-serif">Dear All,</font>
<div class="moz-forward-container">
<div dir="ltr">
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif"> 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.</font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif"> 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. </font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif"> 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. </font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif"> The seminar
will meet on Wednesdays 11:00 AM- 12:15 PM Princeton time
starting on Oct. 14, 2020. </font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif"> 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. </font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif"> Here is the
plan for the first five talks: </font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif">Oct. 14 , Alex
Lubotky (Hebrew University & IAS)</font></div>
<div><font face="Helvetica, Arial, sans-serif">
Title: Introduction to stability and testability</font></div>
<div><font face="Helvetica, Arial, sans-serif">
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. </font></div>
<div><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
<div><font face="Helvetica, Arial, sans-serif">Oct. 21 ,
Jonathan Mosheiff (CS, Carnegie Mellon) </font></div>
<div><font face="Helvetica, Arial, sans-serif"> <span
style="font-size:14px;letter-spacing:0.2px"> Title: </span><span
style="color:rgb(80,0,80)">Stability and testability - a
computational perspective</span></font></div>
<div dir="ltr">
<div dir="ltr"><font face="Helvetica, Arial, sans-serif"><span
style="color:rgb(80,0,80)">
<div><b> Abstract: </b><span
style="color:rgb(34,34,34)">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 </span><i
style="color:rgb(34,34,34)">property testing</i><span
style="color:rgb(34,34,34)">.</span></div>
</span><span style="color:rgb(80,0,80)">
<div>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 <i>testable</i> if
there is an algorithm (called a <i>tester</i>)
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.<br>
</div>
<div>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.<br>
</div>
<div style="direction:ltr">We conclude by presenting
some natural open questions motivated by this work.</div>
<div style="direction:ltr"><br>
</div>
<div>Oct. 28, Oren Beker ( Cambridge U. ) </div>
<div> Title:<span
style="color:rgb(34,34,34)"> </span><span
style="color:rgb(34,34,34)">Stability, testability
and property (T)</span></div>
</span> 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.<br>
The same is true when Sym(n) is replaced by the unitary
group U(n) with the normalized Hilbert--Schmidt metric.<br>
We will recall the relevant terminology, sketch the proof
in a special case, and extend the instability result to
show non-testability.<br>
The discussion will lead us naturally to a slightly weaker
form of stability, called flexible stability, and we will
survey its recent study.<br>
<span style="color:rgb(80,0,80)">
<div><span style="color:rgb(34,34,34)">Based on joint
works with Alex Lubotzky and Jonathan Mosehiff</span> </div>
<div><br>
</div>
<div><br>
</div>
<div>Nov. 4, Adrian Ioana (UCSD) </div>
<div> <span style="color:rgb(34,34,34)">Title:
Stability and sofic approximations for product
groups and property (tau).</span></div>
</span></font>
<div><font face="Helvetica, Arial, sans-serif">
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 <span
style="font-size: 14px;">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. </span><span
style="font-size: 14px;">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 </span><font
style="font-size:14px">strengthens the above in the
case when G is </font><span style="font-size: 14px;">the
direct product of the free group on two generators
with itself.</span><font style="font-size:14px"> 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.</font><br>
</font></div>
<div><font style="font-size:14px" face="Helvetica, Arial,
sans-serif"><br>
</font></div>
<div><font style="font-size:14px" face="Helvetica, Arial,
sans-serif"> Nov. 11, Peter Burton ( U. of Texas) </font></div>
<div><font style="font-size:14px" face="Helvetica, Arial,
sans-serif"> </font><font
face="Helvetica, Arial, sans-serif"><span style="color:
rgb(0, 0, 0); font-size: 12pt;">Title: Flexible
stability and nonsoficity</span></font></div>
<div style="font-size: 12pt; color: rgb(0, 0, 0);"><font
face="Helvetica, Arial, sans-serif"><span
style="font-size:12pt"> 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. </span><br>
</font></div>
<div style="font-size: 12pt; color: rgb(0, 0, 0);"><font
face="Helvetica, Arial, sans-serif"><span
style="font-size:12pt">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.</span><span style="font-size:12pt"> </span><br>
</font></div>
<div style="font-size: 12pt; color: rgb(0, 0, 0);"><font
face="Helvetica, Arial, sans-serif"><span
style="font-size:12pt"><br>
</span></font></div>
<div style="direction:ltr"><font face="Helvetica, Arial,
sans-serif"><br>
</font>
<div dir="ltr">
<div dir="ltr">
<div style="font-size: 12pt; color: rgb(0, 0, 0);"><font
face="Helvetica, Arial, sans-serif"><span
style="font-size:12pt"><br>
</span></font></div>
<div style="font-size: 12pt; color: rgb(0, 0, 0);"><font
face="Helvetica, Arial, sans-serif"><span
style="font-size:12pt">If you are interested to
get regular e-mails about the seminar, please
let me know. Yours, Alex Lubotzky
(<a class="moz-txt-link-abbreviated" href="mailto:alex.lubotzky@mail.huji.ac.il">alex.lubotzky@mail.huji.ac.il</a>)<br>
</span></font></div>
<font face="Helvetica, Arial, sans-serif"><br>
</font> </div>
</div>
</div>
<font face="Helvetica, Arial, sans-serif"><span
style="color:rgb(80,0,80)"></span></font></div>
</div>
<div style="outline:none;padding:10px 0px;width:22px;margin:2px
0px 0px"><font face="Helvetica, Arial, sans-serif"><br>
</font></div>
</div>
</div>
</body>
</html>