BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se i
Calcreator 2.29.30//
CALSCALE:GREGORIAN
UID:3e674ef8-be86-4bc3-9c8c-cabc810fafe7
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:946f5ac9-b9e2-462e-8c47-ed93a83f6d9f
DTSTAMP:20210117T165433Z
CREATED:20200827T124710Z
DESCRIPTION:Topic: A Parallel Repetition Theorem for the GHZ Game\n\nSpeake
rs: Justin Holmgren\n\nAffiliation: Massachusetts Institute of Technology
\n\nWe prove that parallel repetition of the (3-player) GHZ game reduces\n
the value of the game polynomially fast to 0. That is\, the value of\nthe
GHZ game repeated in parallel t times is at most $t^{-\Omega(1)}.\nPreviou
sly\, only a bound of roughly 1 / alpha(t)\, where alpha is the\ninverse A
ckermann function\, was known.\n\nThe GHZ game was recently identified by
Dinur\, Harsha\, Venkat and Yuen\nas a multi-player game where all existin
g techniques for proving\nstrong bounds on the value of the parallel repet
ition of the game\nfail. Indeed\, to prove our result we use a completely
new proof\ntechnique. Dinur et al. speculated that progress on bounding th
e value\nof the parallel repetition of the GHZ game may lead to further\np
rogress on the general question of parallel repetition of\nmulti-player ga
mes. They suggested that the strong correlations\npresent in the GHZ quest
ion distribution represent the ``hardest\ninstance'' of the multi-player p
arallel repetition problem.\n\nAnother motivation for studying the paralle
l repetition of the GHZ\ngame comes from the field of quantum information.
The GHZ game\, first\nintroduced by Greenberger\, Horne and Zeilinger\, i
s a central game in\nthe study of quantum entanglement and has been studie
d in numerous\nworks. For example\, it is used for testing quantum entangl
ement and\nfor device-independent quantum cryptography. In such applicatio
ns a\ngame is typically repeated to reduce the probability of error\, and
\nhence bounds on the value of the parallel repetition of the game may\nbe
useful.\n
DTSTART:20201019T151500Z
DTEND:20201019T161500Z
LAST-MODIFIED:20210106T050202Z
LOCATION:Simonyi Hall 101 and Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-463
END:VEVENT
BEGIN:VEVENT
UID:09e65e58-2542-4d12-bf40-8ba95da1730b
DTSTAMP:20210117T165433Z
CREATED:20200827T131806Z
DESCRIPTION:Topic: The threshold for the square of a Hamilton cycle\n\nSpea
kers: Jinyoung Park\n\nAffiliation: Member\, School of Mathematics\n\nWe w
ill talk about a recent result of Jeff Kahn\, Bhargav Narayanan\,\nand mys
elf stating that the threshold for the random graph G(n\,p) to\ncontain th
e square of a Hamilton cycle is 1/sqrt n\, resolving a\nconjecture of Kühn
and Osthus from 2012. For context\, we will first\nspend some time discus
sing a recent result of Keith Frankston and the\nthree aforementioned auth
ors on a conjecture of Talagrand (a\nfractional version of Kahn-Kalai 'exp
ectation-threshold conjecture').\n
DTSTART:20201020T143000Z
DTEND:20201020T163000Z
LAST-MODIFIED:20210106T050254Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-458
END:VEVENT
BEGIN:VEVENT
UID:ed53f8d8-41da-4ca9-8ef0-1ff3787a1b29
DTSTAMP:20210117T165433Z
CREATED:20200901T214334Z
DESCRIPTION:Topic: Stability and testability - a computational perspective
\n\nSpeakers: Jonathan Mosheiff\n\nAffiliation: Carnegie Mellon University
\n\nIn this talk we survey the recent connection (a joint work with Becker
\nand Lubotzky) between certain group theoretic notions related to\nstabil
ity\, and a novel class of problems from the realm of _property\ntesting._
Consider the computational problem where we are given a\ntuple of permuta
tions in $Sym(n)$\, and wish to determine whether these\npermutations sati
sfy a certain system of equations $E$. We say that\n$E$ is _testable_ if t
here is an algorithm (called a _tester_) that\nqueries only a constant num
ber of entries of the given permutations\,\nand probabilistically distingu
ishes between the case where the\npermutations satisfy $E$\, and the case
in which they are epsilon-far\nfrom any tuple of permutations satisfying $
E$. Note that in our\ndefinition of this problem we depart from the more c
lassical setting\nof property testing\, where the object to be tested is e
ither a\nfunction or a graph. We observe an intriguing connection between
the\ngroup presented by $E$\, which we denote $G$\, and the above\ncomputa
tional problem. It turns out that $G$ is stable if and only if\na certain
natural algorithm is a tester for $E$. Thus\, established\nresults about t
he stability of certain groups yield testers for\ncorresponding systems of
equations. Further exploring this connection\,\nwe discover that the test
ability of $E$ can be fully characterized in\nterms of the group $G$. Stud
ying this characterization yields both\npositive and negative results. For
example\, amenability of $G$ implies\nthat $E$ is testable. On the other
hand\, if $G$ has property (T) and\nfinite quotients of unbounded cardinal
ity\, then $E$ is not testable.\nWe conclude by presenting some natural op
en questions motivated by\nthis work.\n
DTSTART:20201021T150000Z
DTEND:20201021T161500Z
LAST-MODIFIED:20210104T013425Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-0
END:VEVENT
BEGIN:VEVENT
UID:11039d5e-7e80-4098-b024-a0ed9d74209a
DTSTAMP:20210117T165433Z
CREATED:20200827T124824Z
DESCRIPTION:Topic: Fractionally Log-Concave and Sector-Stable Polynomials:
Counting Planar Matchings and More\n\nSpeakers: Nima Anari\n\nAffiliation:
Stanford University\n\nWe introduce two new notions for polynomials assoc
iated with discrete\nset-valued probability distributions. These notions g
eneralize\nwell-studied properties like real-stability and log-concavity\,
but\nunlike them robustly degrade under a number of useful transformation
s\napplied to the polynomial/distribution. We show that these notions\nimp
ly polynomial time approximate sampling and counting algorithms\nthrough r
apid mixing of multi-site Glauber dynamics. We establish the\nnew notions
for polynomials/distributions related to matchings\,\nPfaffian point proce
sses\, and partition-constrained strongly Rayleigh\nmeasures with O(1) par
titions. As the main application we show how to\napproximately count match
ings of a desired size k\, or sample from the\nmonomer-dimer distribution\
, in arbitrary planar graphs (not\nnecessarily bipartite) in polynomial ti
me\; this answers a question\nraised by Jerrum in 1987 who proved intracta
bility of exact counting\nin the planar case. Joint work with Yeganeh Alim
ohammadi\, Kirankumar\nShiragur\, and Thuy-Duong Vuong.\n
DTSTART:20201026T151500Z
DTEND:20201026T161500Z
LAST-MODIFIED:20210106T050346Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-464
END:VEVENT
BEGIN:VEVENT
UID:255d86a4-6ac6-4961-96de-303bd5cddcd3
DTSTAMP:20210117T165433Z
CREATED:20200827T131715Z
DESCRIPTION:Topic: On the extension complexity of random polytopes\n\nSpeak
ers: Lisa Sauermann\n\nAffiliation: Member\, School of Mathematics\n\nSome
times\, it is possible to represent a complicated polytope as a\nprojectio
n of a much simpler polytope. To quantify this phenomenon\,\nthe extension
complexity of a polytope P is defined to be the minimum\nnumber of facets
in a (possibly higher-dimensional) polytope from\nwhich P can be obtained
as a (linear) projection. In this talk\, I will\nfirst give some backgrou
nd on extension complexity and explain its\nconnection to the notion of no
n-negative rank. I will then discuss\nsome results on the extension comple
xity of random polytopes (which\nare obtained as the convex hull of indepe
ndent random points either in\nthe unit ball or on the unit sphere)\, whic
h are joint work with\nMatthew Kwan and Yufei Zhao. Our results prove that
the extension\ncomplexity of these random polytopes is typically on the o
rder of the\nsquare root of number of vertices of the polytope.\n
DTSTART:20201027T143000Z
DTEND:20201027T163000Z
LAST-MODIFIED:20210106T050437Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-459
END:VEVENT
BEGIN:VEVENT
UID:3d532041-1392-4c6c-a351-f28434993e79
DTSTAMP:20210117T165433Z
CREATED:20200901T214428Z
DESCRIPTION:Topic: Stability\, testability and property (T)\n\nSpeakers: Or
en Beker\n\nAffiliation: University of Cambridge\n\nWe show that if $G=\la
ngle S | E\rangle$ is a discrete group with\nProperty (T) then $E$\, as a
system of equations over $S$\, is not\nstable (under a mild condition). Th
at is\, $E$ has approximate\nsolutions in symmetric groups $Sym(n)$\, $n \
geq 1$\, that are far from\nevery solution in $Sym(n)$ under the normalize
d Hamming metric. The\nsame is true when $Sym(n)$ is replaced by the unita
ry group $U(n)$\nwith the normalized Hilbert--Schmidt metric. We will reca
ll the\nrelevant terminology\, sketch the proof in a special case\, and ex
tend\nthe instability result to show non-testability. The discussion will
\nlead us naturally to a slightly weaker form of stability\, called\nflexi
ble stability\, and we will survey its recent study. Based on\njoint works
with Alex Lubotzky and Jonathan Mosehiff.\n
DTSTART:20201028T150000Z
DTEND:20201028T161500Z
LAST-MODIFIED:20210104T014200Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-1
END:VEVENT
BEGIN:VEVENT
UID:f73f11d7-8c02-4315-b198-ecbadb5d0fbd
DTSTAMP:20210117T165433Z
CREATED:20200827T131416Z
DESCRIPTION:Topic: Anti-concentration and the Gap-Hamming problem\n\nSpeake
rs: Anup Rao\n\nAffiliation: University of Washington\n\nWe prove new lowe
r bounds on the well known Gap-Hamming problem in\ncommunication complexit
y. Our main technical result is an\nanti-concentration bound for the inner
product of two independent\nrandom vectors. We show that if A\, B are arb
itrary subsets of the cube\n{±1}^n with |A| · |B| ≥ 2^(1.01n)\, and X ∈ A
and Y ∈ B are\nsampled independently and uniformly\, then the inner produc
t must\nbe anti-concentrated: it takes on any fixed value with prob
ability at\nmost O(1/sqrt(n)). In fact\, the following stronger claim hold
s: for\nany integer k\, |Pr[=k] - Pr[ = k+4]| is at most O(1/n
).\nRemarkably\, this last claim is false if 4 is replaced with an integer
\nthat is not divisible by 4. I will explain why this happens in my\ntalk.
\n\nThis is joint work with Amir Yehudayoff.\n
DTSTART:20201102T161500Z
DTEND:20201102T171500Z
LAST-MODIFIED:20210106T050529Z
LOCATION:Simonyi Hall 101 and Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-465
END:VEVENT
BEGIN:VEVENT
UID:97287033-f4c2-4169-b968-1e6f43bc1762
DTSTAMP:20210117T165433Z
CREATED:20200827T131741Z
DESCRIPTION:Topic: No seminar - Election Day\n\n
DTSTART:20201103T153000Z
DTEND:20201103T173000Z
LAST-MODIFIED:20210106T050621Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-460
END:VEVENT
BEGIN:VEVENT
UID:8a7ec6cb-11dc-4335-81ea-e3192c536335
DTSTAMP:20210117T165433Z
CREATED:20200901T214448Z
DESCRIPTION:Topic: Stability and sofic approximations for product groups an
d property (tau)\n\nSpeakers: Adrian Ioana\n\nAffiliation: University of C
alifornia\, San Diego\n\nA countable group $G$ is called sofic if it admit
s a sofic\napproximation: a sequence of asymptotically free almost actions
on\nfinite sets. Given a sofic group $G$\, it is a natural problem to try
\nto classify all its sofic approximations and\, more generally\, its\nasy
mptotic homomorphisms to finite symmetric groups. Ideally\, one\nwould aim
to show that any almost homomorphism from $G$ to a finite\nsymmetric grou
p is close to an actual homomorphism. If this is the\ncase\, then $G$ is c
alled stable in permutations\, or P-stable. In this\ntalk\, I will first p
resent a result providing a large class of product\ngroups are not P-stabl
e. In particular\, the direct products of the\nfree group on two generator
s with itself and with the group of\nintegers are not P-stable. This impli
es that P-stability is not closed\nunder the direct product construction\,
which answers a question of\nBecker\, Lubotzky and Thom. I will also pres
ent a more recent result\,\nwhich strengthens the above in the case when $
G$ is the direct product\nof the free group on two generators with itself.
This shows\, answering\na question of Bowen\, that $G$ admits a sofic app
roximation which is\nnot essentially a “branched cover” of a sofic approxi
mation by\nhomomorphisms.\n
DTSTART:20201104T160000Z
DTEND:20201104T171500Z
LAST-MODIFIED:20210104T014836Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-2
END:VEVENT
BEGIN:VEVENT
UID:8e076d21-421a-4fe4-a0b1-76b19ca4f180
DTSTAMP:20210117T165433Z
CREATED:20200827T124950Z
DESCRIPTION:Topic: Associativity testing\n\nSpeakers: Ben Green\n\nAffiliat
ion: University of Oxford\n\nSuppose we have a cancellative binary associa
tive operation * on a\nfinite set X. We say that it is delta-associative i
f the proportion of\ntriples x\, y\, z such that x*(y*z) = (x*y)*z is at l
east delta.\n\nGowers and Long studied somewhat associative operations\, a
nd we will\ndescribe their main result. They also suggested an example of
a\nsomewhat associative operation which they conjectured does not (in a\ns
ense I will make precise) resemble a group operation. I will describe\na p
roof of their conjecture\, which uses a surprisingly large number of\ntool
s from additive combinatorics and group theory.\n
DTSTART:20201109T161500Z
DTEND:20201109T171500Z
LAST-MODIFIED:20210106T050712Z
LOCATION:Simonyi Hall 101 and Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-466
END:VEVENT
BEGIN:VEVENT
UID:71fe656e-5de1-4d37-b548-f55ba4b8111b
DTSTAMP:20210117T165433Z
CREATED:20200827T131651Z
DESCRIPTION:Topic: Modular zeros in the character table of the symmetric gr
oup\n\nSpeakers: Sarah Peluse\n\nAffiliation: Member\, School of Mathemati
cs\n\nMiller computed the character table of $S_n$ for some fairly large n
's\nand noticed that almost all of the entries were even. Based on this\,
\nhe conjectured that the proportion of even entries in the character\ntab
le of $S_n$ tends to $1$ as $n\to\infty$. I'll present two proof of\nthis
conjecture\, one of which shows more generally that almost every\nentry of
the character table of $S_n$ is divisible by $p$ for all\nprimes $p$ up t
o $13$. Interestingly\, this proof naturally breaks down\npast $p=13$. I w
ill also discuss the problem of determining the\ndensity of zeros in the c
haracter table of $S_n$. Miller also has\ncomputational data suggesting th
at this density is a positive number\nless than $1$. No background on the
representation theory of $S_n$\nwill be assumed--since the talk is two hou
rs\, I will spend the first\npart introducing this topic.\n
DTSTART:20201110T153000Z
DTEND:20201110T173000Z
LAST-MODIFIED:20210106T050804Z
LOCATION:Remote Access Only - see link below
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-461
END:VEVENT
BEGIN:VEVENT
UID:ccb4f59e-0d61-487f-b302-968b12bba02c
DTSTAMP:20210117T165433Z
CREATED:20200901T214521Z
DESCRIPTION:Topic: Flexible stability and nonsoficity\n\nSpeakers: Peter Bu
rton\n\nAffiliation: University of Texas at Austin\n\nA sofic approximatio
n to a countable discrete group is a sequence of\nfinite models for the gr
oup that generalizes the concept of a Folner\nsequence witnessing amenabil
ity of a group and the concept of a\nsequence of quotients witnessing resi
dual finiteness of a group. If a\ngroup admits a sofic approximation it is
called sofic. It is a well\nknown open problem to determine if every grou
p is sofic. A sofic group\n$G$ is said to be flexibly stable if every sofi
c approximation to $G$\ncan converted to a sequence of disjoint unions of
Schreier graphs on\ncoset spaces of $G$ by modifying an asymptotically van
ishing\nproportion of edges. We will discuss a joint result with Lewis Bow
en\nthat if $\mathrm{PSL}_d(\mathbb{Z})$ is flexibly stable for some $d\n\
geq 5$ then there exists a group which is not sofic.\n
DTSTART:20201111T160000Z
DTEND:20201111T171500Z
LAST-MODIFIED:20210104T021321Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-3
END:VEVENT
BEGIN:VEVENT
UID:61ceda15-22f9-4de5-838f-32f7dfeb59cc
DTSTAMP:20210117T165433Z
CREATED:20200827T131434Z
DESCRIPTION:Topic: Indistinguishability Obfuscation from Well-Founded Assum
ptions\n\nSpeakers: Huijia (Rachel) Lin\n\nAffiliation: University of Wash
ington\n\nIndistinguishability obfuscation\, introduced by [Barak et. al.
\nCrypto’2001]\, aims to compile programs into unintelligible ones\nwhile
preserving functionality. It is a fascinating and powerful\nobject that ha
s been shown to enable a host of new cryptographic goals\nand beyond. Howe
ver\, constructions of indistinguishability obfuscation\nhave remained elu
sive\, with all other proposals relying on heuristics\nor newly conjecture
d hardness assumptions.\n\nIn this work\, we show how to construct indisti
nguishability\nobfuscation from subexponential hardness of four well-found
ed\nassumptions. We prove:\n\nTHEOREM (Informal) Let p be a prime of magni
tude \Theta(2^n)\, where n\nis the security parameter. Assume sub-exponent
ial security of the\nfollowing assumptions: \n\n1. the Learning With Erro
rs (LWE) assumption over Z_p with\nsubexponential modulus-to-noise ratio\,
\n\n2. the Learning Parity with Noise (LPN) assumption over Z_p with\npol
ynomially many LPN samples and inverse polynomial error rate\,\n\n3. the
existence of a Boolean Pseudo-Random Generator (PRG) in NC0\nwith polynomi
al stretch\,\n\n4. the Symmetric eXternal Diffie-Hellman (SXDH) assumptio
n on\nasymmetric bilinear groups of order p.\n\nThen\, (subexponentially s
ecure) indistinguishability obfuscation for\nall polynomial-size circuits
exists.\n\nFurther\, assuming only polynomial security of the aforemention
ed\nassumptions\, there exists collusion resistant public-key functional\n
encryption for all polynomial-size circuits. \n\nJoint work with Aayush Ja
in and Amit Sahai at UCLA.\n
DTSTART:20201116T161500Z
DTEND:20201116T181500Z
LAST-MODIFIED:20210106T050855Z
LOCATION:Simonyi Hall 101 and Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-467
END:VEVENT
BEGIN:VEVENT
UID:fa0304e0-dd52-4fb8-a1e6-b1f26f435d57
DTSTAMP:20210117T165433Z
CREATED:20200827T131829Z
DESCRIPTION:Topic: Factorization through L2\, Rounding and Duality\n\nSpeak
ers: Vijay Bhattiprolu\n\nAffiliation: Member\, School of Mathematics\n\nL
et X and Y be normed spaces. In functional analysis\, a ``theorem on\nfact
orization through L2'' refers to the following type of\nstatement: \n\nEve
ry bounded linear operator A mapping X to Y (i.e. sup_x\n||A(x)||_Y/||x||_
X < infinity)\, can be written as the composition\n(A=B.C) of bounded line
ar operators C mapping X to L2 and B mapping L2\nto Y. \n\nSuch factorizat
ion theorems and their variants (for various choices of\nnormed spaces X a
nd Y) are useful not only in functional analysis\n(where they were develop
ed to study norms on tensor product spaces X\n\otimes X)\, but in several
areas of computer science like discrepancy\ntheory\, communication complex
ity\, column subset selection and\noptimization. In this talk I will discu
ss a generic recipe (using\nrounding+duality) for proving factorization th
eorems. My goal is to\nprovide a streamlined exposition of a classical fac
torization theorem\nof Grothendieck and time permitting show a new factori
zation result\nwhich has applications to quadratic maximization over conve
x sets. \n\nBased on recent joint work with Euiwoong Lee and Assaf Naor.
\n
DTSTART:20201117T153000Z
DTEND:20201117T173000Z
LAST-MODIFIED:20210106T050949Z
LOCATION:Simonyi Hall 101 and Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-462
END:VEVENT
BEGIN:VEVENT
UID:503ff76c-5d3d-463d-92f3-03e55d2a744a
DTSTAMP:20210117T165433Z
CREATED:20200901T214545Z
DESCRIPTION:Topic: Surface groups are flexibly stable\n\nSpeakers: Nir Laza
rovich\n\nAffiliation: Technion\n\nIn this talk I will present a joint wor
k with Arie Levit and Yair\nMinsky on flexible stability of surface groups
. The proof will be\ngeometric in nature and will rely on an analysis of b
ranched covers of\nhyperbolic surfaces. Along the way we will see a quanti
tative variant\nof the LERF property for surface groups which may be of in
dependent\ninterest.\n
DTSTART:20201118T160000Z
DTEND:20201118T171500Z
LAST-MODIFIED:20210104T021956Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-4
END:VEVENT
BEGIN:VEVENT
UID:922591ee-4687-4c22-b26d-eebd8de29c2f
DTSTAMP:20210117T165433Z
CREATED:20200827T131449Z
DESCRIPTION:Topic: New isoperimetric inequalities for convex bodies\n\nSpea
kers: Amir Yehudayoff\n\nAffiliation: Technion - Israel Institute of Techn
ology\n\nWhat can we say on a convex body from seeing its projections? In
the\n80s\, Lutwak introduced a collection of measurements that capture thi
s\nquestion. He called them the affine quermassintegrals. They are affine
\ninvariant analogues of the classical quermassintegrals (a.k.a.\nintrinsi
c volumes) from the Brunn-Minkowski theory. Lutwak conjectured\nthat among
all convex bodies of a given volume\, they are minimized\nprecisely on el
lipsoids. The known cases of this conjecture correspond\nto the Blaschke-S
antalo and Petty projection inequalities. Petty's\ninequality\, for exampl
e\, is a strict generalization of the classical\nisoperimetric inequality.
Our main result confirms Lutwak's\nconjecture\, including a characterizat
ion of the equality cases\, in a\nsingle unified framework. Among other th
ings\, we also prove that\nellipsoids are the only local minimizers.\n\nJo
int work with Emanuel Milman.\n
DTSTART:20201123T161500Z
DTEND:20201123T171500Z
LAST-MODIFIED:20210106T051039Z
LOCATION:Remote Access Only - see link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-468
END:VEVENT
BEGIN:VEVENT
UID:4178c489-5968-4b17-bb87-a5b720ec96dc
DTSTAMP:20210117T165433Z
CREATED:20200827T131956Z
DESCRIPTION:Topic: Factorization through L2\, Rounding and Duality Part 2\n
\nSpeakers: Vijay Bhattiprolu\n\nAffiliation: Member\, School of Mathemati
cs\n\nLet X and Y be normed spaces. In functional analysis\, a ``theorem o
n\nfactorization through L2'' refers to the following type of\nstatement:
\n\nEvery bounded linear operator A mapping X to Y (i.e. sup_x\n||A(x)||_Y
/||x||_X < infinity)\, can be written as the composition\n(A=B.C) of bound
ed linear operators C mapping X to L2 and B mapping L2\nto Y. \n\nSuch fac
torization theorems and their variants (for various choices of\nnormed spa
ces X and Y) are useful not only in functional analysis\n(where they were
developed to study norms on tensor product spaces X\n\otimes X)\, but in s
everal areas of computer science like discrepancy\ntheory\, communication
complexity\, column subset selection and\noptimization. In this talk I wil
l discuss a generic recipe (using\nrounding+duality) for proving factoriza
tion theorems. My goal is to\nprovide a streamlined exposition of a classi
cal factorization theorem\nof Grothendieck and time permitting show a new
factorization result\nwhich has applications to quadratic maximization ove
r convex sets.\n\nBased on recent joint work with Euiwoong Lee and Assaf N
aor.\n
DTSTART:20201124T153000Z
DTEND:20201124T173000Z
LAST-MODIFIED:20210106T051131Z
LOCATION:Remote Access Only - see link below
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-463
END:VEVENT
BEGIN:VEVENT
UID:7ea0b43a-e13b-4f4a-9303-64a3002f68b1
DTSTAMP:20210117T165433Z
CREATED:20200901T214606Z
DESCRIPTION:Topic: Approximations of groups\, subquotients of infinite dire
ct products and equations over groups\n\nSpeakers: Lev Glebsky\n\nAffiliat
ion: Universidad Autónoma de San Luis Potosí\n\nLet C be a class of groups
. (For example\, C is a class of all finite\ngroups\, or C is a class of a
ll finite symmetric groups.) I give a\ndefinition of approximations of a g
roup G by groups from C. For\nexample\, the groups approximable by symmetr
ic groups are\, by\ndefinition\, sofic groups.\n\nFor some classes C the f
ollowing result holds:\n\nG is approximable by C if and only if G is a sub
group of some quotient\nof a (infinite) direct product of groups from C.\n
\nIt also may be formulated using equations over groups. In the talk I\np
lan to explain this in details and discuss some related results and\nopen
questions.\n
DTSTART:20201125T160000Z
DTEND:20201125T171500Z
LAST-MODIFIED:20210104T022725Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-5
END:VEVENT
BEGIN:VEVENT
UID:94cc7298-3328-4293-9d53-2309452d9f30
DTSTAMP:20210117T165433Z
CREATED:20200827T125037Z
DESCRIPTION:Topic: Thresholds for Random Subspaces\, aka\, LDPC Codes Achie
ve List-Decoding Capacity\n\nSpeakers: Mary Wootters\n\nAffiliation: Stanf
ord University\n\nWhat combinatorial properties are likely to be satisfied
by a random\nsubspace over a finite field? For example\, is it likely tha
t not too\nmany points lie in any Hamming ball of fixed radius? What about
any\ncombinatorial rectangle of fixed side length? We give a simple\ncha
racterization of the threshold on the dimension below which this is\nvery
likely and above which this is very unlikely. Our motivation\ncomes from e
rror correcting codes\, and we use this characterization to\nestablish the
list-decodability of random Low Density Parity-Check\n(LDPC) codes\, up t
o list-decoding capacity.\n\nThis talk is based on the joint work with Jon
athan Mosheiff\, Nicolas\nResch\, Noga Ron-Zewi\, and Shashwat Silas.\n
DTSTART:20201130T161500Z
DTEND:20201130T171500Z
LAST-MODIFIED:20210106T051221Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-469
END:VEVENT
BEGIN:VEVENT
UID:c08f6e97-71e4-4952-a590-a826ed847c2e
DTSTAMP:20210117T165433Z
CREATED:20200827T132021Z
DESCRIPTION:Topic: Getting the most from our data\n\nSpeakers: Paul Valiant
\n\nAffiliation: Member\, School of Mathematics\n\nI will discuss techniqu
es\, structural results\, and open problems from\ntwo of my recent papers\
, in the context of a broader area of work on\nthe motivating question: 'h
ow do we get the most from our data?'\n\nIn the first part of the talk\, I
will revisit the basic statistical\nproblem of estimating the mean of a r
eal-valued distribution. I will\nintroduce an estimator with the guarantee
that 'our estimator\, on\n*any* distribution\, is as accurate as the samp
le mean is for the\nGaussian distribution of matching variance.' Crucially
\, in contrast to\nprior works\, our estimator does not require prior know
ledge of the\nvariance\, and works across the entire gamut of distribution
s with\nfinite variance\, including those without any higher moments.\nPar
ameterized by the sample size $n$\, the failure probability\n$\delta$\, an
d the variance $\sigma^2$\, our estimator is accurate to\nwithin $\sigma\c
dot(1+o(1))\sqrt{\frac{2\log\frac{1}{\delta}}{n}}$\,\nwhich is tight up to
the $1+o(1)$ factor.\n\nIn the second part of the talk I will introduce a
framework for\nstatistical estimation that leverages knowledge of how sam
ples are\ncollected but makes no distributional assumptions on the data va
lues.\nAs a motivating example: suppose one wishes to conduct an accurate
\npolitical poll of a population\, estimating the fraction of the\npopulat
ion that would answer 'yes' to a certain question\; however\, one\ndoes no
t have access to uniformly random people from the population\,\nbut instea
d only has access to a set of people S drawn from some\ndistribution D\, a
distribution on subsets of the population. For\nexample\, D could describ
e a viral process on a social network\, where\nrespondents are the - highl
y correlated - set of people that the viral\nprocess has reached by a give
n time. How can knowledge of the\ndistribution D\, combined with the actua
l sampled set S and their\nsurvey responses\, best be used to estimate the
true population mean?\nOur model encompasses the fact that people's surve
y responses may be\nintricately correlated with their probability of being
in S. We\npresent an efficient $\pi/2$ approximation to this general clas
s of\nquestions\, via a surprising connection to the Grothendieck problem.
\n
DTSTART:20201201T153000Z
DTEND:20201201T173000Z
LAST-MODIFIED:20210106T051312Z
LOCATION:Simonyi Hall 101 and Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-464
END:VEVENT
BEGIN:VEVENT
UID:ef5bc577-1f13-4904-8ab0-954ac7123d88
DTSTAMP:20210117T165433Z
CREATED:20200901T214630Z
DESCRIPTION:Topic: Stability\, cohomology vanishing\, and non-approximable
groups\n\nSpeakers: Andreas Thom\n\nAffiliation: University of Dresden\n\n
Several well-known open questions (such as: are all groups\nsofic/hyperlin
ear?) have a common form: can all groups be approximated\nby asymptotic ho
momorphisms into the symmetric groups $Sym(n)$ (in the\nsofic case) or the
finite dimensional unitary groups $U(n)$ (in the\nhyperlinear case)? In t
he case of $U(n)$\, the question can be asked\nwith respect to different m
etrics and norms. We answers\, for the first\ntime\, one of these versions
\, showing that there exist fintely\npresented groups which are not approx
imated by $U(n)$ with respect to\nthe Frobenius nor. Our strategy is to sh
ow that some higher\ndimensional cohomology vanishing phenomena imply stab
ility\, that is\,\nevery Frobenius-approximate homomorphism into finite-di
mensional\nunitary groups is close to an actual homomorphism. This is comb
ined\nwith existence results of certain non-residually finite central\next
ensions of lattices in some simple $p$-adic Lie groups. These\ngroups act
on high rank Bruhat-Tits buildings and satisfy the needed\nvanishing cohom
ology phenomenon and are thus stable and not\nFrobenius-approximated.\n
DTSTART:20201202T160000Z
DTEND:20201202T171500Z
LAST-MODIFIED:20210104T023304Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-6
END:VEVENT
BEGIN:VEVENT
UID:0efd526d-4b00-4f33-beb9-2c3c6a1fa37c
DTSTAMP:20210117T165433Z
CREATED:20200827T131517Z
DESCRIPTION:Topic: Extractor-based Approach to Proving Memory-Sample Lower
Bounds for Learning\n\nSpeakers: Sumegha Garg\n\nAffiliation: Harvard Univ
ersity\n\nA recent line of work has focused on the following question: Can
one\nprove strong unconditional lower bounds on the number of samples\nne
eded for learning under memory constraints? We study an\nextractor-based a
pproach to proving such bounds for a large class of\nlearning problems as
follows.\n\nA matrix M: A x X -> {-1\,1} corresponds to the following lear
ning\nproblem: An unknown function f in X is chosen uniformly at random. A
\nlearner tries to learn f from a stream of samples\, (a_1\, b_1)\, (a_2\,
\nb_2) ...\, where for every i\, a_i in A is chosen uniformly at random\na
nd b_i = M(a_i\,f). Assume that k\, l\, r are such that any submatrix of\n
M\, with at least 2^{-k}|A| rows and at least 2^{-l}|X| columns\, has a\nb
ias of at most 2^{-r} (extractor property).\n\nWe show that any learning a
lgorithm for the learning problem\ncorresponding to M requires either a me
mory of size at least Ω(k l)\,\nor at least 2^{Ω(r)} samples. We also exte
nd the lower bounds to a\nlearner that is allowed two passes over the stre
am of samples. In\nparticular\, we show that any two-pass algorithm for le
arning parities\nof size n requires either a memory of size Ω(n^{3/2}) or
at least\n2^{Ω(n^{1/2})} samples. An open question would be to go beyond t
hese\ntechniques to prove such memory-sample tradeoffs.\n\nJoint works wit
h Ran Raz and Avishay Tal.\n
DTSTART:20201207T161500Z
DTEND:20201207T171500Z
LAST-MODIFIED:20210106T051403Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-470
END:VEVENT
BEGIN:VEVENT
UID:66ff6eb1-d2a5-4e97-83bc-f3dfc939d2da
DTSTAMP:20210117T165433Z
CREATED:20200827T132041Z
DESCRIPTION:Topic: High Dimensional Expanders and Ramanujan Complexes\n\nSp
eakers: Alexander Lubotzky\n\nAffiliation: Hebrew University\n\nExpander g
raphs in general\, and Ramanujan graphs in particular\, have\nplayed an im
portant role in computer science and pure mathematics in\nthe last four de
cades. In recent years the area of high dimensional\nexpanders (i.e. simpl
ical complexes with properties generalizing those\nof expanding graphs) an
d Ramanujan complexes is starting to emerge.\nThe various motivations of t
his subarea will be surveyed: these\ninclude connections and applications
to cohomology and Gromov's\noverlapping problem on the pure math side and
to property testing and\nerror correcting codes on the CS side.\n
DTSTART:20201208T153000Z
DTEND:20201208T173000Z
LAST-MODIFIED:20210106T051456Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-465
END:VEVENT
BEGIN:VEVENT
UID:7ddee18b-3b6e-47bd-8f54-94cc76422bad
DTSTAMP:20210117T165433Z
CREATED:20200901T214658Z
DESCRIPTION:Topic: Vanishing of cohomology for groups acting on buildings\n
\nSpeakers: Izhar Oppenheim\n\nAffiliation: Ben Gurion University\n\nIn hi
s seminal paper from 1973\, Garland introduced a machinery for\nproving va
nishing of group cohomology for groups acting on Bruhat-Tits\nbuildings. T
his machinery\, known today as “Garland’s method”\,\nhad several applicati
ons as a tool for proving rigidity results (e.g.\,\nproving Kazhdan proper
ty (T) or\, more recently\, group stability\nresults). In my talk\, I will
introduce a variation of Garland’s\nmethod\, explain how it yields vanish
ing cohomology and how it can be\ngeneralized to vanishing of cohomology w
ith Banach coefficients. Parts\nof this talk are based on joint works with
Z. Grinbaum-Reizis and A.\nLubotzky.\n
DTSTART:20201209T160000Z
DTEND:20201209T171500Z
LAST-MODIFIED:20210104T024032Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-7
END:VEVENT
BEGIN:VEVENT
UID:d769b470-d8b8-4af8-9d22-02e493545c0d
DTSTAMP:20210117T165433Z
CREATED:20200901T214718Z
DESCRIPTION:Topic: Hilbert-Schmidt stability of groups via C*-algebras\n\nS
peakers: Tatiana Shulman\n\nAffiliation: Polish Academy of Science\n\nThe
aim of this talk is to show that C*-algebras are useful for\nstudying stab
ility of groups. In particular we will discuss some\nobstructions for Hilb
ert-Schmidt stability of groups\, obtain a\ncomplete characterization of H
ilbert-Schmidt stability for amenable\ngroups in terms of characters\, and
discuss some examples of amenable\nand non-amenable Hilbert-Schmidt stabl
e groups. If time permits we\nalso will consider certain modifications of
Hilbert-Schmidt stability\nwhen matrices are replaced by elements of von N
eumann factors\, as well\nas a relation between Hilbert-Schmidt stability
and operator\nnorm-stability. All necessary information on C*-algebras wil
l be given\nduring the talk. The talk is mostly based on joint works with
Don\nHadwin.\n
DTSTART:20201216T160000Z
DTEND:20201216T171500Z
LAST-MODIFIED:20210104T024709Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-8
END:VEVENT
BEGIN:VEVENT
UID:657a12a4-66f1-4da1-9e08-9b210eab80fa
DTSTAMP:20210117T165433Z
CREATED:20200901T214744Z
DESCRIPTION:Topic: The PCP theorem\, locally testable codes\, and property
testing\n\nSpeakers: Irit Dinur\n\nAffiliation: Weizmann Institute of Scie
nce\n\nIn this lecture I will describe the three concepts appearing in the
\ntitle and how they connect with each other.
DTSTART:20210113T160000Z
DTEND:20210113T171500Z
LAST-MODIFIED:20210113T140916Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-9
END:VEVENT
BEGIN:VEVENT
UID:2fde93da-01a6-4dce-b35b-45ee4fcc2b12
DTSTAMP:20210117T165433Z
CREATED:20210105T232236Z
DESCRIPTION:Topic: Stability and Invariant Random Subgroups\n\nSpeakers: He
nry Bradford\n\nAffiliation: Cambridge University\n\nDetermining whether o
r not a given finitely generated group is\npermutation stable is in genera
l a difficult problem. In this talk we\ndiscuss work of Becker\, Lubotzky
and Thom which gives\, in the case of\namenable groups\, a necessary and s
ufficient condition for permutation\nstability in terms of the invariant r
andom subgroups (IRSs) of the\ngroup. We outline some ideas from the proof
of this criterion\, give an\nintroduction to IRSs in general\, and show h
ow they yield new families\nof examples of stable and unstable groups.
DTSTART:20210120T160000Z
DTEND:20210120T171500Z
LAST-MODIFIED:20210112T202044Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-10
END:VEVENT
BEGIN:VEVENT
UID:6af09e8c-f3ad-47b5-a49f-15147f2a1c7c
DTSTAMP:20210117T165433Z
CREATED:20201102T125150Z
DESCRIPTION:Topic: An Improved Exponential-Time Approximation Algorithm for
Fully-Alternating Games Against Nature\n\nSpeakers: Andrew Drucker\n\nAff
iliation: University of Chicago\n\n'Games against Nature' [Papadimitriou '
85] are two-player games of\nperfect information\, in which one player's m
oves are made randomly.\nEstimating the value of such games (i.e.\, winnin
g probability under\noptimal play by the strategic player) is an important
goal in the\nstudy of decision-making under uncertainty. The problem's\n
PSPACE-completeness does not rule out non-trivial algorithms\, a goal\nful
filled in certain cases by Littman\, Majercik\, and Pitassi [LMP\n'01]. \n
\nWe study the case in which the players strictly alternate with binary\nm
oves\, for which [LMP '01] does not give a general speedup. We give a\nran
domized algorithm to approximate the value of such games (and to\nproduce
near-optimal play) . Our algorithm achieves exponential\nsavings over brut
e-force\, making 2^{(1-delta)n} queries to the input\ngame's lookup table
for some absolute constant delta > 0\, and\ncertifies a lower bound on the
game value with exponentially-small\nexpected additive error. (On the dow
nside\, delta is tiny and the\nalgorithm uses exponential space.)\n\nOur a
lgorithm is recursive\, and bootstraps a 'base-case' algorithm for\nfixed-
size inputs. The base-case algorithm and the form of recursive\ncompositio
n used are interesting and\, we feel\, likely to find uses\nbeyond the pre
sent work.\n
DTSTART:20210125T161500Z
DTEND:20210125T171500Z
LAST-MODIFIED:20210115T131316Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-471
END:VEVENT
BEGIN:VEVENT
UID:5e37d6ea-fe6f-4696-b9ae-08c161c1d8eb
DTSTAMP:20210117T165433Z
CREATED:20201105T141350Z
DESCRIPTION:Topic: Log-concave polynomials in theory and applications\n\nSp
eakers: Cynthia Vinzant\n\nAffiliation: Member\, School of Mathematics\n\n
A polynomial with nonnegative coefficients is strongly log-concave if\nit
and all of its derivatives are log-concave as functions on the\npositive o
rthant. This rich class of polynomials includes many\ninteresting examples
\, such as homogeneous real stable polynomials and\nmixed volume polynomia
ls of convex bodies. Its structure is intimately\nrelated to combinatorial
objects called matroids and generalized\npermutahedra. This theory gives
powerful tools for showing discrete\nlog-concavity of finite sequences. Di
stributions coming from the\ncoefficients of such polynomials can also be
approximately sampled. In\nthis talk I will go over the structural propert
ies of this rich class\nof real polynomials and discuss applications in co
mbinatorics and\ncomputer science.\n\nThis talk is based on joint work wit
h Nima Anari\, Kuikui Liu and\nShayan Oveis Gharan.\n
DTSTART:20210126T153000Z
DTEND:20210126T173000Z
LAST-MODIFIED:20210115T155206Z
LOCATION:Simonyi Hall 101 and Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-466
END:VEVENT
BEGIN:VEVENT
UID:606f0224-e503-463a-86b4-f0ab7fa521fa
DTSTAMP:20210117T165433Z
CREATED:20210105T233015Z
DESCRIPTION:Topic: Stability of amenable groups via ergodic theory\n\nSpeak
ers: Arie Levit \n\nAffiliation: Yale University\n\nI will describe how ba
sic ergodic theory can be used to prove that\ncertain amenable groups are
stable. I will demonstrate our method by\nshowing that lamplighter groups
are stable. Another uncountably\ninfinite family to which our method appli
es are the so-called B.H.\nNeumann groups. This is the first construction
of an uncountable\nfamily of stable groups. The talk is based on joint wor
k with Alex\nLubotzky\, relying on the Invariant-Random-Subgroup criterion
for\nstability developed by Becker-Lubotzky-Thom.
DTSTART:20210127T160000Z
DTEND:20210127T171500Z
LAST-MODIFIED:20210106T000816Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-11
END:VEVENT
BEGIN:VEVENT
UID:f88c5efe-a68d-48b4-b1a2-38f21c1f99d7
DTSTAMP:20210117T165433Z
CREATED:20201102T131735Z
DESCRIPTION:Topic: Graph Density Inequalities\, Sums of Squares and Tropica
lization\n\nSpeakers: Annie Raymond\n\nAffiliation: University of Massachu
setts Amherst\n\nEstablishing inequalities among graph densities is a cent
ral pursuit\nin extremal graph theory. One way to certify the nonnegativit
y of a\ngraph density expression is to write it as a sum of squares or as
a\nrational sum of squares. In this talk\, we will explore how one does so
\nand we will then identify simple conditions under which a graph\ndensity
expression cannot be a sum of squares or a rational sum of\nsquares. Trop
icalization will play a key role for the latter.\n\nThis is joint work wit
h Greg Blekherman\, Mohit Singh\, and Rekha\nThomas.\n
DTSTART:20210201T161500Z
DTEND:20210201T171500Z
LAST-MODIFIED:20210113T161557Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-472
END:VEVENT
BEGIN:VEVENT
UID:43ecc4a2-ace6-48f6-9d23-3df2d300ac09
DTSTAMP:20210117T165433Z
CREATED:20201105T141632Z
DESCRIPTION:Topic: TBA\n\nSpeakers: Cynthia Vinzant\n\nAffiliation: Member\
, School of Mathematics\n\n
DTSTART:20210202T153000Z
DTEND:20210202T173000Z
LAST-MODIFIED:20201207T043021Z
LOCATION:Simonyi Hall 101 and Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-467
END:VEVENT
BEGIN:VEVENT
UID:747162cd-b9da-4234-b824-ef18806a55f0
DTSTAMP:20210117T165433Z
CREATED:20210105T233030Z
DESCRIPTION:Topic: Permutation stability of Grigorchuk groups\n\nSpeakers:
Tianyi Zheng\n\nAffiliation: University of California\, San Diego\n\nA rec
ent result of Becker\, Lubotzky and Thom characterizes\, for\namenable gro
ups\, permutation stability in terms of co-soficity of\ninvariant random s
ubgroups (IRS). We will explain that for a class of\namenable groups actin
g on rooted trees\, including the Grigorchuk\ngroup\, the IRS co-soficity
condition is verified. One key ingredient\nin the proof is the so called “
double commutator” lemma for IRS\,\nwhich is an analogue of the classical
lemma known for normal\nsubgroups. All notions will be defined and explain
ed.
DTSTART:20210203T160000Z
DTEND:20210203T171500Z
LAST-MODIFIED:20210106T000847Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-12
END:VEVENT
BEGIN:VEVENT
UID:d5814a96-97ee-43eb-8a85-ccda979bc196
DTSTAMP:20210117T165433Z
CREATED:20201102T134103Z
DESCRIPTION:Topic: TBA\n\nSpeakers: Robert Kleinberg\n\nAffiliation: Cornel
l University\n\n
DTSTART:20210208T161500Z
DTEND:20210208T171500Z
LAST-MODIFIED:20210104T134932Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-473
END:VEVENT
BEGIN:VEVENT
UID:73f680b1-1569-46b9-a71a-5d8e3fc62ad0
DTSTAMP:20210117T165433Z
CREATED:20201105T141703Z
DESCRIPTION:Topic: TBA\n\nSpeakers: Shai Evra\n\nAffiliation: Princeton Uni
versity\n\n
DTSTART:20210209T153000Z
DTEND:20210209T173000Z
LAST-MODIFIED:20210104T135442Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-468
END:VEVENT
BEGIN:VEVENT
UID:0329d698-f7ac-4744-b35a-7da7d41abc86
DTSTAMP:20210117T165433Z
CREATED:20210105T233045Z
DESCRIPTION:Topic: Non-amenable groups admitting no sofic approximation by
expander graphs\n\nSpeakers: Gabor Kun\n\nAffiliation: Alfréd Rényi Instit
ute of Mathematics\n\nWe show that the direct product of an infinite\, fin
itely generated\nKazhdan Property (T) group and a finitely presented\, not
residually\nfinite amenable group admits no sofic approximation by expand
er\ngraphs. Joint work with Andreas Thom.
DTSTART:20210210T160000Z
DTEND:20210210T171500Z
LAST-MODIFIED:20210106T000909Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-13
END:VEVENT
BEGIN:VEVENT
UID:d3be163f-2f2b-4082-a0b2-b9b76b43c1eb
DTSTAMP:20210117T165433Z
CREATED:20201111T155153Z
DESCRIPTION:Topic: TBA\n\nSpeakers: Arkadev Chattopadhyay\n\nAffiliation: T
ata Institute of Fundamental Research\n\n
DTSTART:20210215T161500Z
DTEND:20210215T171500Z
LAST-MODIFIED:20210104T135526Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-474
END:VEVENT
BEGIN:VEVENT
UID:7981e94f-3eb5-4a6e-a324-f635c71e6e88
DTSTAMP:20210117T165433Z
CREATED:20201105T141752Z
DESCRIPTION:Topic: TBA\n\nSpeakers: Shai Evra\n\nAffiliation: Princeton Uni
versity\n\n
DTSTART:20210216T153000Z
DTEND:20210216T173000Z
LAST-MODIFIED:20210104T135740Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-469
END:VEVENT
BEGIN:VEVENT
UID:c2bd80c0-7a7e-45bd-9400-528ccbb34ac9
DTSTAMP:20210117T165433Z
CREATED:20210105T233102Z
DESCRIPTION:Topic: To Be Announced\n\n
DTSTART:20210217T160000Z
DTEND:20210217T171500Z
LAST-MODIFIED:20210105T233112Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-14
END:VEVENT
BEGIN:VEVENT
UID:4c2ca9e1-4fc7-40d4-bb45-157d41a62ac3
DTSTAMP:20210117T165433Z
CREATED:20201105T141054Z
DESCRIPTION:Topic: TBA\n\nSpeakers: Zongchen Chen\n\nAffiliation: Georgia I
nstitute of Technology\n\n
DTSTART:20210222T161500Z
DTEND:20210222T171500Z
LAST-MODIFIED:20210104T140020Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-475
END:VEVENT
BEGIN:VEVENT
UID:7fddaff2-f6bc-4211-9d74-171a5aa0e7f4
DTSTAMP:20210117T165433Z
CREATED:20201105T142008Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210223T153000Z
DTEND:20210223T173000Z
LAST-MODIFIED:20201207T044112Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-470
END:VEVENT
BEGIN:VEVENT
UID:938715a4-7eba-48d5-bb74-3e9bd53be50a
DTSTAMP:20210117T165433Z
CREATED:20210105T233119Z
DESCRIPTION:Topic: To Be Announced\n\n
DTSTART:20210224T160000Z
DTEND:20210224T171500Z
LAST-MODIFIED:20210105T233128Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-15
END:VEVENT
BEGIN:VEVENT
UID:7ce81e8f-5a8f-4b52-b907-a55a1d5e08f7
DTSTAMP:20210117T165433Z
CREATED:20201102T134602Z
DESCRIPTION:Topic: TBA\n\nSpeakers: Benny Sudakov\n\nAffiliation: ETH Züri
ch\n\n
DTSTART:20210301T161500Z
DTEND:20210301T171500Z
LAST-MODIFIED:20210104T140209Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-476
END:VEVENT
BEGIN:VEVENT
UID:38361dcd-e874-4ba6-9ab3-5047c220731d
DTSTAMP:20210117T165433Z
CREATED:20201105T142037Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210302T153000Z
DTEND:20210302T173000Z
LAST-MODIFIED:20201207T044128Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-471
END:VEVENT
BEGIN:VEVENT
UID:7c00e5b6-2f83-4ad6-9398-8c69f2e36575
DTSTAMP:20210117T165433Z
CREATED:20210105T233137Z
DESCRIPTION:Topic: To Be Announced\n\n
DTSTART:20210303T160000Z
DTEND:20210303T171500Z
LAST-MODIFIED:20210105T233146Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-16
END:VEVENT
BEGIN:VEVENT
UID:ad5a315f-e75e-4ddc-a4a8-e8e5e948ae43
DTSTAMP:20210117T165433Z
CREATED:20201102T134915Z
DESCRIPTION:Topic: TBA\n\nSpeakers: Venkatesan Guruswami\n\nAffiliation: Ca
rnegie Mellon University\n\n
DTSTART:20210308T161500Z
DTEND:20210308T171500Z
LAST-MODIFIED:20210104T140253Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-477
END:VEVENT
BEGIN:VEVENT
UID:18a5160e-eeb3-42e9-97c7-007ee910d130
DTSTAMP:20210117T165433Z
CREATED:20201105T142117Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210309T153000Z
DTEND:20210309T173000Z
LAST-MODIFIED:20201207T044142Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-472
END:VEVENT
BEGIN:VEVENT
UID:8c81621f-6d49-48e8-8ad7-7fcd90b5f396
DTSTAMP:20210117T165433Z
CREATED:20210105T233155Z
DESCRIPTION:Topic: To Be Announced\n\n
DTSTART:20210310T160000Z
DTEND:20210310T171500Z
LAST-MODIFIED:20210105T233204Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-17
END:VEVENT
BEGIN:VEVENT
UID:4a3184f4-4f8b-477c-b610-bab3476f24ee
DTSTAMP:20210117T165433Z
CREATED:20201211T181634Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210315T151500Z
DTEND:20210315T161500Z
LAST-MODIFIED:20201211T181751Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-478
END:VEVENT
BEGIN:VEVENT
UID:19a0b1ed-e3c5-4805-ab40-3e3ab0d55312
DTSTAMP:20210117T165433Z
CREATED:20201211T183906Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210316T143000Z
DTEND:20210316T163000Z
LAST-MODIFIED:20201211T183923Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-473
END:VEVENT
BEGIN:VEVENT
UID:7d6eaddf-d38a-4b5c-8f6e-038a371ddd72
DTSTAMP:20210117T165433Z
CREATED:20210105T233215Z
DESCRIPTION:Topic: To Be Announced\n\n
DTSTART:20210317T150000Z
DTEND:20210317T161500Z
LAST-MODIFIED:20210105T233222Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-18
END:VEVENT
BEGIN:VEVENT
UID:12816126-204a-4d11-8cd5-9a926a44fb5c
DTSTAMP:20210117T165433Z
CREATED:20201211T183006Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210322T151500Z
DTEND:20210322T161500Z
LAST-MODIFIED:20201211T183028Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-479
END:VEVENT
BEGIN:VEVENT
UID:46af48c2-7d37-4acd-b8f7-97f7458a3ff9
DTSTAMP:20210117T165433Z
CREATED:20201211T183932Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210323T143000Z
DTEND:20210323T163000Z
LAST-MODIFIED:20201211T183950Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-474
END:VEVENT
BEGIN:VEVENT
UID:a12c80e7-9f7c-475d-a28b-09b1ace01e4c
DTSTAMP:20210117T165433Z
CREATED:20210105T233231Z
DESCRIPTION:Topic: To Be Announced\n\n
DTSTART:20210324T150000Z
DTEND:20210324T161500Z
LAST-MODIFIED:20210105T233238Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-19
END:VEVENT
BEGIN:VEVENT
UID:8dde43e2-5c4f-4524-bb35-0788b7b718b8
DTSTAMP:20210117T165433Z
CREATED:20201211T183039Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210329T151500Z
DTEND:20210329T161500Z
LAST-MODIFIED:20201211T183100Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-480
END:VEVENT
BEGIN:VEVENT
UID:359899be-da9e-4ced-af6c-52d048940123
DTSTAMP:20210117T165433Z
CREATED:20201211T184005Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210330T143000Z
DTEND:20210330T163000Z
LAST-MODIFIED:20201211T184022Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-475
END:VEVENT
BEGIN:VEVENT
UID:92b0101d-92e1-4208-96a2-f9f580e58817
DTSTAMP:20210117T165433Z
CREATED:20210105T233246Z
DESCRIPTION:Topic: To Be Announced\n\n
DTSTART:20210331T150000Z
DTEND:20210331T161500Z
LAST-MODIFIED:20210105T233255Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-20
END:VEVENT
BEGIN:VEVENT
UID:aa70b88d-1f2d-4dd8-9b73-09edb446e184
DTSTAMP:20210117T165433Z
CREATED:20201211T183110Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210405T151500Z
DTEND:20210405T161500Z
LAST-MODIFIED:20201211T183129Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-481
END:VEVENT
BEGIN:VEVENT
UID:2334c3d2-1a6d-425e-bd62-dea331b79356
DTSTAMP:20210117T165433Z
CREATED:20201211T184029Z
DESCRIPTION:Topic: TBA\n\n
DTSTART:20210406T143000Z
DTEND:20210406T163000Z
LAST-MODIFIED:20201215T181257Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-476
END:VEVENT
BEGIN:VEVENT
UID:fe701db0-c0d4-4f5e-8e91-827d35a18c57
DTSTAMP:20210117T165433Z
CREATED:20210105T233304Z
DESCRIPTION:Topic: To Be Announced\n\n
DTSTART:20210407T150000Z
DTEND:20210407T161500Z
LAST-MODIFIED:20210105T233311Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-21
END:VEVENT
BEGIN:VEVENT
UID:dffa9fba-67d0-4db8-8bdf-8dd7b9955001
DTSTAMP:20210117T165433Z
CREATED:20201211T183141Z
DESCRIPTION:Topic: TBA\n\nSpeakers: Katrina Legitt\n\nAffiliation: Hebrew U
niversity\n\n
DTSTART:20210412T151500Z
DTEND:20210412T161500Z
LAST-MODIFIED:20210104T140403Z
LOCATION:Remote Access - see Zoom link below
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-482
END:VEVENT
END:VCALENDAR