BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se i
Calcreator 2.30.4//
CALSCALE:GREGORIAN
UID:20b20f5a-4ba1-42f2-b59a-7868749f3b62
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:d6efdda9-1f95-4551-91cd-219a9b008e9a
DTSTAMP:20210417T030118Z
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:20210120T133546Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-10
END:VEVENT
BEGIN:VEVENT
UID:91fde910-1164-4856-9a40-970e30f8f423
DTSTAMP:20210417T030118Z
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:20210125T154319Z
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:d5bf95fb-5466-49fe-92ae-d74a0a2d3913
DTSTAMP:20210417T030118Z
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:20210126T145659Z
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-466
END:VEVENT
BEGIN:VEVENT
UID:0443113d-f352-4c34-8fc9-ab256da04232
DTSTAMP:20210417T030118Z
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:20210127T142451Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-11
END:VEVENT
BEGIN:VEVENT
UID:4f7cce18-0d49-4ccd-bb14-9a222eba2e2f
DTSTAMP:20210417T030118Z
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:20210201T143745Z
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:25fd47b6-e6ff-4858-a183-135df334ad7a
DTSTAMP:20210417T030118Z
CREATED:20201105T141632Z
DESCRIPTION:Topic: Log-concave polynomials in theory and applications - Par
t 2\n\nSpeakers: Cynthia Vinzant\n\nAffiliation: Member\, School of Mathem
atics\n\nA polynomial with nonnegative coefficients is strongly log-concav
e if\nit and all of its derivatives are log-concave as functions on the\np
ositive orthant. This rich class of polynomials includes many\ninteresting
examples\, such as homogeneous real stable polynomials and\nmixed volume
polynomials of convex bodies. Its structure is intimately\nrelated to comb
inatorial objects called matroids and generalized\npermutahedra. This theo
ry gives powerful tools for showing discrete\nlog-concavity of finite sequ
ences. Distributions coming from the\ncoefficients of such polynomials can
also be approximately sampled. In\nthis talk I will go over the structura
l properties of this rich class\nof real polynomials and discuss applicati
ons in combinatorics and\ncomputer science.\n\nThis talk is based on joint
work with Nima Anari\, Kuikui Liu and\nShayan Oveis Gharan.\n
DTSTART:20210202T153000Z
DTEND:20210202T173000Z
LAST-MODIFIED:20210202T210509Z
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:cd994aae-4af9-464c-85eb-6ccd9bae478c
DTSTAMP:20210417T030118Z
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:20210203T141152Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-12
END:VEVENT
BEGIN:VEVENT
UID:be1fbe81-1cf7-4eb7-a82f-1b7e0cb3c4bd
DTSTAMP:20210417T030118Z
CREATED:20201102T134103Z
DESCRIPTION:Topic: Total Functions in the Polynomial Hierarchy\n\nSpeakers:
Robert Kleinberg\n\nAffiliation: Cornell University\n\nNon-constructive e
xistence proofs\, which establish the existence of\nobjects without furnis
hing an efficient algorithm to produce examples\,\nabound in mathematics.
How hard is it\, computationally\, to find\nobjects whose existence is gua
ranteed non-constructively? Since the\n1980's complexity theorists have be
en classifying these search\nproblems into broad classes of computationall
y equivalent problems\,\neach corresponding to a different non-constructiv
e proof principle\,\nsuch as the pigeonhole principle\, the local search p
rinciple (that any\nfunction on a finite graph has a local minimum)\, and
the parity\nprinciple (that a finite set of odd cardinality cannot be empt
y). All\nof these problems are contained in the complexity class TFNP\,\nc
onsisting of search problems for which a solution is guaranteed to\nexist
and the validity of a solution can be efficiently verified. \n\nOne of the
most successful non-constructive methods for proving\nexistence of combin
atorial objects\, the probabilistic method\, does not\nseem to be captured
by TFNP because the applications of the\nprobabilistic method often yield
existence of objects whose properties\nare hard to verify computationally
. For example\, Erdos famously used\nthe probabilistic method to prove the
existence of 'Ramsey graphs'\nhaving no large cliques or independent sets
\; however\, it is hard to\nverify that a given graph is a Ramsey graph. T
his motivates exploring\nthe complexity of search problems for which exist
ence of solutions is\nstill guaranteed but efficient verification of solut
ions is no longer\npossible. Many such problems can be organized into a hi
erarchy\ndepending on the number of alternating quantifiers in the logical
\nformula that solutions must satisfy. At the second level of the\nhierarc
hy we encounter a class that seems especially rich in such\nproblems: PEPP
(for “polynomial empty pigeonhole principle”)\,\nwhich includes problems
related to probabilistic-method proofs based\non the union bound. Examples
include finding a bit string that is far\nfrom all codewords\, finding an
explicit rigid matrix\, as well as a\nproblem we call Complexity\, captur
ing Complexity Theory’s quest to\nfind functions that cannot be computed b
y small circuits. When the\nunion bound is generous\, in that solutions co
nstitute at least a\npolynomial fraction of the domain\, we have a family
of seemingly\nweaker classes α-PEPP. Higher in the hierarchy\, we identify
the\nconstructive version of the Sauer-Shelah lemma and the appropriate\n
generalization of PPP that contains it\, as well as the problem of\nfindin
g a king in a tournament (a vertex k such that all other\nvertices are def
eated by k\, or by somebody k defeated).\n\nJoint work with Oliver Korten\
, Dan Mitropolsky\, and Christos\nPapadimitriou.\n
DTSTART:20210208T161500Z
DTEND:20210208T171500Z
LAST-MODIFIED:20210208T151550Z
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:74c51d82-5fc0-4d4f-be24-ea18d3195c1d
DTSTAMP:20210417T030118Z
CREATED:20201105T141703Z
DESCRIPTION:Topic: High dimensional expanders\n\nSpeakers: Shai Evra\n\nAff
iliation: Princeton University\n\nExpander graphs are graphs which simulta
neously are both sparse and\nhighly connected. The theory of expander grap
hs received a lot of\nattention in the past half a century\, from both com
puter science and\nmathematics. In recent years\, a new theory of high dim
ensional\nexpanders have emerged. In his seminal work\, Gromov raised the
\nfollowing main question: Do (bounded degree) high dimensional\nexpanders
exist? A culmination of several works by experts in the\nfield resulted
in a positive answer to Gromov's question (according to\nhis definition).
\n\nIn this talk\, I will give a quick introduction to the theory of high
\ndimensional expanders\, describe the challenges this theory\noffers\, an
d explain the known techniques to construct such (bounded\ndegree) high di
mensional expanders. \n\nThis talk is based on a joint work with Tali Kauf
man.\n
DTSTART:20210209T153000Z
DTEND:20210209T173000Z
LAST-MODIFIED:20210209T132833Z
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:623a16cd-a32a-46c8-ac79-24c0297ec2c6
DTSTAMP:20210417T030118Z
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:20210210T134529Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-13
END:VEVENT
BEGIN:VEVENT
UID:a6389c21-d7f7-4b58-bcd5-c19b21893460
DTSTAMP:20210417T030118Z
CREATED:20201111T155153Z
DESCRIPTION:Topic: Monotone Arithmetic Circuit Lower Bounds Via Communicati
on Complexity\n\nSpeakers: Arkadev Chattopadhyay\n\nAffiliation: Tata Inst
itute of Fundamental Research\n\nValiant (1980) showed that general arithm
etic circuits with negation\ncan be exponentially more powerful than monot
one ones. We give the\nfirst qualitative improvement to this classical res
ult: we construct a\nfamily of polynomials P-n in n variables\, each of it
s monomials has\npositive coefficient\, such that P-n can be computed by a
\npolynomial-size *depth-three* formula but every monotone circuit\ncomput
ing it has size exp(n^{1/4}/log(n)).\n\nThe polynomial P-n embeds the SINK
o XOR function devised recently by\nChattopadhyay\, Mande and Sherif (201
9) to refute the\nLog-Approximate-Rank Conjecture in communication complex
ity. To prove\nour lower bound for P-n\, we develop a general connection b
etween\ncorruption of combinatorial rectangles by any function f o XOR and
\ncorruption of product polynomials by a certain polynomial P-f that is\na
n arithmetic embedding of f. This connection should be of independent\nint
erest.\n\nUsing further ideas from communication complexity\, we construct
\nanother family of set-multilinear polynomials f(n\,m) such that both\nF(
n\,m) − eps. f(n\,m) and F(n\,m) + eps.f(n\,m) have monotone circuit\ncomp
lexity exp(n/log(n)) if eps >= exp−(Omega(m)) and F(n\,m) is\nthe full se
t-multilinear polynomial over n blocks each of size m\, with\nm=O(nlogn).
The polynomials f(n\,m) have 0/1 coefficients and are in\nVNP. Proving su
ch lower bounds for monotone circuits has been\nadvocated recently by Hrub
eš (2020) as a first step towards proving\nlower bounds against general ci
rcuits via his new approach.\n\n(This is joint work with Rajit Datta and P
artha Mukhopadhyay and is\naccessible at: https://eccc.weizmann.ac.il/repo
rt/2020/166/)\n
DTSTART:20210215T161500Z
DTEND:20210215T171500Z
LAST-MODIFIED:20210216T152245Z
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:7dc5635f-15b1-42f0-b9fe-36094bd60a60
DTSTAMP:20210417T030118Z
CREATED:20201105T141752Z
DESCRIPTION:Topic: High dimensional expanders - Part 2\n\nSpeakers: Shai Ev
ra\n\nAffiliation: Princeton University\n\nExpander graphs are graphs whic
h simultaneously are both sparse and\nhighly connected. The theory of expa
nder graphs received a lot of\nattention in the past half a century\, from
both computer science and\nmathematics. In recent years\, a new theory of
high dimensional\nexpanders have emerged. In his seminal work\, Gromov ra
ised the\nfollowing main question: Do (bounded degree) high dimensional\ne
xpanders exist? A culmination of several works by experts in the\nfield r
esulted in a positive answer to Gromov's question (according to\nhis defin
ition).\n\nIn this talk\, I will give a quick introduction to the theory o
f high\ndimensional expanders\, describe the challenges this theory\noffer
s\, and explain the known techniques to construct such (bounded\ndegree) h
igh dimensional expanders. \n\nThis talk is based on a joint work with Tal
i Kaufman.\n
DTSTART:20210216T153000Z
DTEND:20210216T173000Z
LAST-MODIFIED:20210216T152923Z
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:6efbe057-e2c7-4baa-b232-dcd16bce1222
DTSTAMP:20210417T030118Z
CREATED:20210105T233102Z
DESCRIPTION:Topic: Matrix stability of crystallographic groups\n\nSpeakers:
Soren Eilers\n\nAffiliation: University of Copenhagen\n\nSome years ago\,
I proved with Shulman and Sørensen that precisely 12\nof the 17 wallpaper
groups are matricially stable in the operator\nnorm. We did so as part of
a general investigation of when group\n$C^*$-algebras have the semiprojec
tivity and weak matricial\nsemiprojectivity properties — notions which are
standard tools in\nthe classification theory for $C^*$-algebras.\n\nOur r
esults were largely negative\, and recently Dadarlat has provided\na frame
work for understanding the obstructions to matricial stability\nfor discre
te groups. With this perspective\, our results may be seen\nas showing th
at\, at least in this case\, stability ensues when the\nobstructions allow
it.\n\nI intend to go through the proof of this positive result in a form
\naimed at non-$C^*$-algebraists. It must be admitted that the proof is\nv
ery $C^*$-algebraic in nature\, but it goes through a natural\ndimension r
eduction technique (invented by Friis and Rørdam in the\nmid-90’s) which I
can definitely explain and expect could be useful\nin other settings as w
ell.\n
DTSTART:20210217T160000Z
DTEND:20210217T171500Z
LAST-MODIFIED:20210217T142404Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-14
END:VEVENT
BEGIN:VEVENT
UID:ad267095-773a-4e51-98c6-e1f56cf871ac
DTSTAMP:20210417T030118Z
CREATED:20201105T141054Z
DESCRIPTION:Topic: Optimal Mixing of Glauber Dynamics: Entropy Factorizatio
n via High-Dimensional Expansion\n\nSpeakers: Zongchen Chen\n\nAffiliation
: Georgia Institute of Technology\n\nWe consider the Glauber dynamics (als
o called Gibbs sampling) for\nsampling from a discrete distribution in hig
h-dimensional space (e.g.\,\nselecting a uniformly random legal coloring o
r independent set in a\ngiven graph\, or selecting a 'typical' state in a
given statistical\nphysics model\, like spin systems). In these probabilis
tic\nalgorithms\, each step picks uniformly at random a single variable\,
\nand updates it conditional on all other variables. Note that\, if the\nn
umber of variables (= the dimension) is n\, such MCMC (Monte Carlo\nMarkov
Chain) algorithms perform a random walk on an exponential (in\nn) size sp
ace.\n\nWe show an optimal mixing time bound for the Glauber dynamics in a
\nvariety of settings. Our work presents an improved version of the\nspect
ral independence approach of Anari et al. (2020) and shows\nO(nlogn) mixin
g time for graphical models/spin systems on any n-vertex\ngraph of bounded
degree\, when the maximum eigenvalue of an associated\ninfluence matrix i
s bounded. Our proof approach combines classic tools\nof entropy tensoriza
tion/factorization and recent developments of\nhigh-dimensional expanders.
\n\nBased on joint work with Kuikui Liu and Eric Vigoda. \n
DTSTART:20210222T161500Z
DTEND:20210222T171500Z
LAST-MODIFIED:20210222T160126Z
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:b86d982a-a009-40d3-8e0e-b73181a80050
DTSTAMP:20210417T030118Z
CREATED:20201105T142008Z
DESCRIPTION:Topic: Introduction to Laplacian Linear Systems for Undirected
Graphs\n\nSpeakers: John Peebles\n\nAffiliation: Member\, School of Mathem
atics\n\nThis talk gives an introduction on how to quickly solve linear sy
stems\nwhere the matrix of the system is the Laplacian matrix of any\nundi
rected graph. No prior familiarity with optimization is assumed.\nIn the p
rocess\, we will cover:\n\n * what positive semidefinite matrices are and
why mathematicians say\nthey 'behave like nonnegative numbers' (mainly int
ended as a review)\n * the Loewner ordering (standard PSD ordering) on pos
itive\nsemidefinite matrices and how it provides a natural definition of\n
'multiplicative approximation' for them\n * Richardson iteration / gradien
t descent for solving quadratic\nminimization problems\n * preconditioning
and why we care about the sparsity of the matrix\nwhen trying to solve li
near systems quickly\n * spectral sparsification of graphs (presented/used
as a black box\nstatement)\n * the Peng-Spielman algorithm for solving la
placian linear systems\nin nearly linear time. (Solves a Laplacian linear
system with m\nnonzero entries in m*polylog(m) time. This is only slightly
more than\nthe time it takes to write down the system. Compared to the be
st\nruntime achievable using fast matrix multiplication algorithms\, even
\nif the exponent for matrix multiplication is 2\, the Peng-Speilman\nalgo
rithm is much faster in sparse graphs. Even in dense graphs\, it is\nnever
slower by more than a polylogarithmic factor.)\n\n
DTSTART:20210223T153000Z
DTEND:20210223T173000Z
LAST-MODIFIED:20210223T132831Z
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-470
END:VEVENT
BEGIN:VEVENT
UID:1006b7e7-042b-4f97-9d2d-29f422db834e
DTSTAMP:20210417T030118Z
CREATED:20210105T233119Z
DESCRIPTION:Topic: Norm stability in the unitary case from Voiculescu to Gr
omov-Lawson\n\nSpeakers: Shmuel Weinberger\n\nAffiliation: University of C
hicago\n\nThis expository talk will try to bridge the first examples of 'a
lmost\ncommuting' unitary matrices that are not almost 'commuting unitarie
s'\ndue to Voiculescu to a more sophisticated and very beautiful\nconstruc
tion of examples by Gromov and Lawson in the early 80's that\nis intimatel
y connected to deep phenomena in topology and geometry\nrelated to the rol
e of fundamental group. It can serve as an\nintroduction to Dadarlat's tal
k.\n\nIf I inadvertently say anything new and correct\, it will be joint w
ork\nwith Alex Lubotzky or Guoliang Yu. However\, I expect that most of th
e\ntalk will be about ideas well known before half the audience was born.
\n
DTSTART:20210224T160000Z
DTEND:20210224T171500Z
LAST-MODIFIED:20210224T135730Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-15
END:VEVENT
BEGIN:VEVENT
UID:691b1836-0079-44df-992b-546a61b1b9ca
DTSTAMP:20210417T030118Z
CREATED:20201102T134602Z
DESCRIPTION:Topic: Rainbow structures\, Latin squares & graph decomposition
s\n\nSpeakers: Benny Sudakov\n\nAffiliation: ETH Zürich\n\nA subgraph of
an edge-coloured graph is called rainbow if all its\nedges have distinct c
olours. The study of rainbow subgraphs goes\nback to the work of Euler on
Latin squares in the 18th century. \nSince then rainbow structures were t
he focus of extensive research and\nfound numerous applications in design
theory and graph\ndecompositions. In this talk we discuss how probabilisti
c reasoning\ncan be used to attack several old problems in this area\, lea
ding to\nsubstantial progress on several well-known conjectures of Ryser\,
\nBrouwer\, Ringel\, and Graham-Sloane.\n\nBased on joint works with Keeva
sh\, Montgomery\, Pokrovskiy and\nYepremian.\n
DTSTART:20210301T161500Z
DTEND:20210301T171500Z
LAST-MODIFIED:20210301T152330Z
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:910f6bb1-d9bd-4964-9cc7-08d5efca3b81
DTSTAMP:20210417T030118Z
CREATED:20201105T142037Z
DESCRIPTION:Topic: Solving Laplacian Systems of Directed Graphs\n\nSpeakers
: John Peebles\n\nAffiliation: Member\, School of Mathematics\n\nThis talk
introduces a directed analog of the\nclassical Laplacian matrix and discu
sses algorithms for solving\ncertain problems related to them. Of particul
ar interest is that using\nsuch algorithms\, one can compute the stationar
y distribution of a\nMarkov chain to high accuracy with a number of arithm
etic operations\nclose to the number of possible transitions. The analogou
s problem in\nthe low space setting\, in contrast\, remains open.\n
DTSTART:20210302T153000Z
DTEND:20210302T173000Z
LAST-MODIFIED:20210302T133007Z
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-471
END:VEVENT
BEGIN:VEVENT
UID:d23f74ae-a676-40d4-bdc5-62037218229b
DTSTAMP:20210417T030118Z
CREATED:20210105T233137Z
DESCRIPTION:Topic: Topological obstructions to matrix stability of discrete
groups\n\nSpeakers: Marius Dadarlat \n\nAffiliation: Purdue University\n
\nA discrete countable group is matricially stable if its finite\ndimensio
nal approximate unitary representations are perturbable to\ngenuine repres
entations in the point-norm topology. We aim to explain\nin accessible ter
ms why matricial stability for a group $G$ implies\nthe vanishing of the r
ational even cohomology of $G$ for large classes\nof groups\, including th
e linear groups.
DTSTART:20210303T160000Z
DTEND:20210303T171500Z
LAST-MODIFIED:20210303T134625Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-16
END:VEVENT
BEGIN:VEVENT
UID:8091423e-9291-476b-848c-a19979451023
DTSTAMP:20210417T030118Z
CREATED:20201102T134915Z
DESCRIPTION:Topic: Strong refutation of semi-random Boolean CSPs\n\nSpeaker
s: Venkatesan Guruswami\n\nAffiliation: Carnegie Mellon University\n\nFor
a fixed integer k > 1\, the Boolean k-XOR problem consists of a\nsystem of
linear equations mod 2 with each equation involving exactly\nk variables.
We give an algorithm to strongly refute *semi-random*\ninstances of the B
oolean k-XOR problem on n variables that have\nn^{k/2} poly(log n) equatio
ns. (In a semi-random k-XOR instance\, the\nequations can be arbitrary and
only the right-hand sides are random.)\nVia known reductions\, this yield
s an efficient strong refutation\nalgorithm for semi-random instances of a
ll Boolean constraint\nsatisfaction problems. The number of constraints re
quired by our\nalgorithm matches\, up to polylogarithmic factors\, the bes
t-known\nbounds for efficient refutation of fully random instances.\n\nWhe
n k is even\, refutation of k-XOR follows via a natural flattening\nto a 2
-XOR instance on n^{k/2} variables. Such a straightforward\napproach is\,
however\, not available for odd k. The fully random case\nof k-XOR for odd
k was refuted in prior work via spectral methods\nemploying intricate tra
ce-moment computations. We first give a simpler\nproof for the purely rand
om case relying only on an off-the-shelf\nmatrix Bernstein inequality. Spr
ingboarding off the random case\, we\nidentify a combinatorial property of
random k-XOR instances that makes\nspectral refutation work\, and solve t
he semi-random case by reduction\nto a collection of 2-XOR instances and e
mploying spectral upper bounds\nthat utilize the Booleanity of the assignm
ent.\n\nJoint work with Jackson Abascal and Pravesh Kothari.\n
DTSTART:20210308T161500Z
DTEND:20210308T171500Z
LAST-MODIFIED:20210308T182426Z
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:ad6f4718-f8e0-4e70-93d0-98247b683a77
DTSTAMP:20210417T030118Z
CREATED:20201105T142117Z
DESCRIPTION:Topic: Random k-out subgraphs\n\nSpeakers: Or Zamir\n\nAffiliat
ion: Member\, School of Mathematics\n\nRandom sampling a subgraph of a gra
ph is an important algorithmic\ntechnique. Solving some problems on the (
smaller) subgraph is\nnaturally faster\, and can give either a useful appr
oximate answer\, or\nsometimes even give a result that can be quickly modi
fied to an exact\nsolution\, on the original graph.\n\nWe study the follow
ing simple sampling model and question about it: \n\nEach vertex of an ar
bitrary simple graph on n vertices chooses k\nrandom incident edges. \n\n
What is the expected number of edges in the original graph that\nconnect d
ifferent connected components of the sampled subgraph?\n\nWe prove that th
e answer is O(n/k)\, when k ≥ c log n\, for some large\nenough c. We con
jecture that the same holds for smaller values of\nk\, possibly for any k
≥ 2. Such a result is best possible for any k\n≥ 2.\n\nAs an application\,
we use this sampling result to obtain a one-way\ncommunication protocol w
ith private randomness for finding a spanning\nforest of a graph in which
each vertex sends only O( \sqrt(n) log n)\nbits to a referee. \n\nBased o
n joint work with Jacob Holm\, Valeria King\, Mikkel Thorup and\nUri Zwick
.\n
DTSTART:20210309T153000Z
DTEND:20210309T173000Z
LAST-MODIFIED:20210309T145849Z
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-472
END:VEVENT
BEGIN:VEVENT
UID:89cf3f9c-4611-4bd0-8aaa-cb7c54aea47d
DTSTAMP:20210417T030118Z
CREATED:20210105T233155Z
DESCRIPTION:Topic: Constraint metric approximation and constraint stability
\n\nSpeakers: Liviu Paunescu\n\nAffiliation: Romanian Academy\n\nConstrain
t metric approximation is about constructing an approximation\nof a group
$G$\, when the approximation is already given for a subgroup\n$H$. Similar
ly\, constraint stability is about lifting a representation\nof a group $G
$\, when the lift is already provided for a subgroup $H$.\nJoint work with
Goulnara Arzhantseva.
DTSTART:20210310T160000Z
DTEND:20210310T171500Z
LAST-MODIFIED:20210310T134625Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-17
END:VEVENT
BEGIN:VEVENT
UID:d9995e77-60ac-428c-8ef9-f0f3fa5c2c3c
DTSTAMP:20210417T030118Z
CREATED:20201211T181634Z
DESCRIPTION:Topic: Local Proofs with Arbitrarily Small Encoding Overhead\n
\nSpeakers: Noga Ron-Zewi\n\nAffiliation: Haifa University\n\nThe celebrat
ed PCP theorem from the 90's shows that any mathematical\nproof can be enc
oded in such a way that its correctness can be\nverified locally by readin
g only a tiny number of bits from the\nencoding. This foundational result
has had a transformative effect on\ntheoretical computer science with dive
rse applications in complexity\ntheory and cryptography. \n\nA fundamental
question that has drawn a great amount of interest is\nwhat is the minima
l overhead in encoding that is needed to allow for\nsuch highly efficient
local verification. While the original PCP\ntheorem only guarantees a poly
nomial overhead\, a beautiful line of\nwork has culminated in remarkably s
hort encodings with only a\npoly-logarithmic overhead. \n\nMotivated by re
cent practical implementations of such proof systems\,\nwe study a relativ
ely new interactive variant of PCPs\, called\nInteractive Oracle Proofs\,
and show that for this model the overhead\nin the encoding can be made arb
itrarily small (approaching 1). Our\nproof leverages recent constructions
of high-rate locally testable and\ndecodable codes. \n\nJoint work with R
on Rothblum.\n
DTSTART:20210315T151500Z
DTEND:20210315T161500Z
LAST-MODIFIED:20210315T151535Z
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-478
END:VEVENT
BEGIN:VEVENT
UID:e7373b66-2885-47ab-94af-bef2fba2ad38
DTSTAMP:20210417T030118Z
CREATED:20201211T183906Z
DESCRIPTION:Topic: Polynomial systems and mixed volumes\n\nSpeakers: Ricky
I Liu\n\nAffiliation: Member\, School of Mathematics\n\nBernstein's theore
m (also known as the\nBernstein-Khovanskii-Kushnirenko theorem) gives a bo
und on the number\nof nonzero solutions of a polynomial system of equation
s in terms of\nthe mixed volume of its Newton polytopes. In this talk\, we
will give\nsome background on polynomial systems and mixed volumes and th
en\nsketch a proof of Bernstein's theorem. We will also discuss some\nappl
ications to enumerative combinatorics\, including a bound on the\nnumber o
f doubly monic Laurent polynomials whose initial powers have\nvanishing co
nstant term in terms of Eulerian numbers.\n
DTSTART:20210316T143000Z
DTEND:20210316T163000Z
LAST-MODIFIED:20210316T124025Z
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-473
END:VEVENT
BEGIN:VEVENT
UID:8440020b-cce0-4512-afc7-e1b43b707396
DTSTAMP:20210417T030118Z
CREATED:20210105T233215Z
DESCRIPTION:Topic: Approximate representations of symplectomorphisms via qu
antization\n\nSpeakers: Leonid Polterovich\n\nAffiliation: Tel Aviv Univer
sity\n\nWe argue that quantization\, a mathematical model of the quantum\n
classical correspondence\, gives rise to approximate unitary\nrepresentati
ons of symplectomorphism groups. As an application\, we get\nan obstructio
n to symplectic action of Lubotzky-Oppenheim non $p$-norm\napproximated gr
oups. Preliminaries on symplectic geometry and\nquantization will be expla
ined. Joint work with Laurent Charles.
DTSTART:20210317T150000Z
DTEND:20210317T161500Z
LAST-MODIFIED:20210317T131217Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-18
END:VEVENT
BEGIN:VEVENT
UID:8d1f1978-4533-44e8-976c-ad0ae6d9adc7
DTSTAMP:20210417T030118Z
CREATED:20201211T183006Z
DESCRIPTION:Topic: The abstract chromatic number\n\nSpeakers: Leonardo Naga
mi Coregliano\n\nAffiliation: University of Chicago\n\nWhat edge density o
f a graph guarantees that that it will contain a\nparticular subgraph? Or
one of a given family $\mathcal{F}$ of\nsubgraphs? The celebrated Erdős--S
tone--Simonovits Theorem\ncharacterizes the maximum edge density in $\math
cal{F}$-free graphs\,\nin terms of the minimum {\em chromatic number} of a
ny graph in the\nfamily $\mathcal{F}$. More recently\, generalizations of
this theorem\nfor ordered graphs\, cyclically ordered graphs\, edge-ordere
d graphs\,\netc. were shown in terms of appropriately defined chromatic nu
mbers.\n\nIn a recent joint work with A. Razborov\, we proved an analogue
of this\ntheorem in the general setting of 'graphs with an arbitrary extra
\nstructure' (formally\, these are encoded by an open interpretation from
\nthe theory of graphs to some universal first-order theory $T$) in\nterms
of an {\em abstract chromatic number}. However\, as its name\nsuggests\,
the initial formula for this abstract chromatic number is so\nabstract tha
t its computability was left as an open question.\n\nIn this talk\, I will
present this generalization of the\nErdős--Stone--Simonovits Theorem\, an
d an alternative formula for the\nabstract chromatic number based on a par
tite version of Ramsey's\nTheorem. This implies the computability of the a
bstract chromatic\nnumber when the underlying universal first-order theory
$T$ is\nfinitely axiomatizable.\n\nThis lecture will require no special b
ackground knowledge.\n
DTSTART:20210322T151500Z
DTEND:20210322T161500Z
LAST-MODIFIED:20210322T114206Z
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-479
END:VEVENT
BEGIN:VEVENT
UID:7018fd7c-3248-434e-ad3e-508807db859c
DTSTAMP:20210417T030118Z
CREATED:20201211T183932Z
DESCRIPTION:Topic: Amortized circuit complexity\, formal complexity measure
s\, and catalytic algorithms\n\nSpeakers: Jeroen Zuiddam\n\nAffiliation: N
ew York University - Courant Institute of Mathematical Sciences\n\nSome of
the central questions in complexity theory address the\namortized complex
ity of computation (also sometimes known as direct\nsum problems). While t
hese questions appear in many contexts\, they are\nall variants of the fol
lowing: \n\nIs the best way of computing T many times in parallel simply t
o\ncompute T independently each time\, or\, can we achieve an economy of\n
scale and compute all copies of T more efficiently on average? \n\nIn this
talk\, we discuss some recent results studying the amortized\ncircuit com
plexity of computing boolean functions in various circuit\nmodels. The amo
rtized circuit complexity of a boolean function f is\ndefined to be the li
mit\, as m tends to infinity\, of the circuit\ncomplexity of computing f o
n the same input m times\, divided by m. We\nprove a new duality theorem f
or amortized circuit complexity in any\ncircuit model composed of gates ov
er a finite gate set\, showing that\nthe amortized circuit complexity of c
omputing f is equal to the best\nlower bound achieved by any 'formal compl
exity measure' applied to f.\nThis new duality theorem is inspired by\, an
d closely related to\,\nStrassen's duality theorem for semirings\, which h
as been fruitfully\nused to characterize the matrix multiplication exponen
t\, the Shannon\nCapacity of graphs\, as well as other important parameter
s in\ncombinatorics and complexity. We discuss how our new duality theorem
\ncan be used to give alternative proofs of upper bounds on amortized\ncir
cuit complexity\, and also the close relationship between amortized\ncircu
it complexity and catalytic algorithms\, in which an algorithm is\nprovide
d with an extra input of advice bits that it is free to use\, as\nlong as
it outputs a new copy of the extra advice on termination. \n\nThis is join
t work with Robert Robere.\n
DTSTART:20210323T143000Z
DTEND:20210323T163000Z
LAST-MODIFIED:20210323T120052Z
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-474
END:VEVENT
BEGIN:VEVENT
UID:aa3a53b1-d0e0-466e-bd8d-bec7790e61f0
DTSTAMP:20210417T030118Z
CREATED:20210105T233231Z
DESCRIPTION:Topic: Why was Connes' embedding conjecture refuted and there a
re still no known non-hyperlinear groups?\n\nSpeakers: Michael Chapman \n
\nAffiliation: Hebrew University\n\nIn [MIP*=RE by JNVWY] the authors cons
truct a non-local game that\nresolves Tsirelson's problem to the negative
and by that refute\nConnes' embedding conjecture (CEC). The game *-algebra
(see e.g.\n[KPS]) enables one to construct a finitely presented *-algebra
from a\ngiven (synchronous) game. The *-algebra of the game from [JNVWY]
is\nrepresentable\, has a trace\, and its von Neumann closure is not\nembe
ddable in an ultraproduct of the hyperfinite\n$\mathrm{II}_1$-factor\, i.e
.\, it is not hyperlinear. If one could\nmanage to generate a game for whi
ch the *-algebra both refutes CEC and\nis the complex group ring of some g
roup $G$\, then one would have found\na non-hyperlinear group. There is a
known way of constructing games\nwhose *-algebra is the group ring of some
group $G$. These are called\n'Linear constraint system games' (See e.g. [
Slofstra\, KPS]). In this\ntalk I am going to:\n\n * Go through the defini
tions of non-local games\, game values and\nTsirelson's problem.\n * Introd
uce the game *-algebra.\n * Study representations of the game *-algebra and
their connection to\nvarious game values.\n * Define linear constraint sys
tem games and discuss some properties\nof their *-algebra (namely\, their
game group).\n * Explain how far the game in [JNVWY] is from being a linear
\nconstraint system game.\n\n
DTSTART:20210324T150000Z
DTEND:20210324T161500Z
LAST-MODIFIED:20210324T124728Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-19
END:VEVENT
BEGIN:VEVENT
UID:653e34f9-4617-414b-a6ea-2c79c5bcbcbc
DTSTAMP:20210417T030118Z
CREATED:20201211T183039Z
DESCRIPTION:Topic: Approximating Max Cut with Subexponential Linear Program
s\n\nSpeakers: Tselil Schramm\n\nAffiliation: Stanford University\n\nIn th
e max cut problem\, we are given an n-vertex graph and we are\nasked what
is the maximum fraction of edges 'cut' by any partition of\nthe vertices?
This problem can be reformulated as an optimization\nproblem over the cut
polytope\, which has exponentially many vertices\nand facets. A classical
result of Goemans and Williamson proves that\nwe can approximate the max c
ut value of a graph within a factor of\n0.878\, by instead optimizing over
a spectrahedral relaxation of\npolynomial complexity. The theory-of-appro
ximation orthodoxy (for good\nreason) predicts that polytope relaxations a
re far inferior\, and small\npolytopes cannot hope to give non-trivial app
roximation to max cut. In\nthis talk\, I will describe a result which defi
es this prediction: we\nshow that polytopes with subexponentially many fac
ets *can* give\nnontrivial approximations to the max cut problem\, as well
as other\ncombinatorial optimization problems. This is in surprising cont
rast to\noptimization problems over the reals\, for which an exponential\n
separation between spectrahedra and polytopes is known.\n
DTSTART:20210329T151500Z
DTEND:20210329T161500Z
LAST-MODIFIED:20210329T120220Z
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-480
END:VEVENT
BEGIN:VEVENT
UID:4035ef44-8bf9-42f4-8cc4-f5a9e965f8e8
DTSTAMP:20210417T030118Z
CREATED:20201211T184005Z
DESCRIPTION:Topic: Computational - Statistical gaps and the Group Testing
problem\n\nSpeakers: Fotis Iliopoulos\n\nAffiliation: Member\, School of M
athematics\n\nIn a plethora of random models for constraint satisfaction a
nd\nstatistical inference problems\, researchers from different communitie
s\nhave observed computational gaps between what existential or\nbrute-for
ce methods promise\, and what known efficient algorithms\nachieve. In this
talk\, I will discuss this phenomenon in the context\nof the so-called Gr
oup Testing problem.\n\nGroup Testing is a fundamental problem in statisti
cal inference with\nmany real-world applications. The goal is to detect a
set of k\ndefective items out of a population of size p using n << p tests
.\nTowards that end\, one is allowed to utilize a procedure that can test
\ngroups of items\, in which each test is returned positive if and only\ni
f at least one item in the group is defective. In this talk\, I will\ndis
cuss the task of _approximate_ recovery\, in which we tolerate\nhaving a s
mall number of incorrectly classified items.\n
DTSTART:20210330T143000Z
DTEND:20210330T163000Z
LAST-MODIFIED:20210331T142820Z
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-475
END:VEVENT
BEGIN:VEVENT
UID:e0efd587-3aba-4c3e-bcc1-4e934313e10c
DTSTAMP:20210417T030118Z
CREATED:20210105T233246Z
DESCRIPTION:Topic: Ultrametric stability problems\n\nSpeakers: Francesco Fo
urnier-Facio\n\nAffiliation: Eidgenössische Technische Hochschule Zürich\n
\nWe study stability problems with respect to families of groups\nequipped
with bi-invariant ultrametrics\, that is\, metrics satisfying\nthe strong
triangle inequality. This property has very strong\nconsequences\, and th
is form of stability behaves very differently from\nthe other ones that we
saw throughout the seminar. Many results can be\nestablished in full gene
rality\, but we will focus on a p-adic analogue\nof Ulam stability\, where
the family of approximating groups is\n$GL_n(Z_p)$.\n
DTSTART:20210331T150000Z
DTEND:20210331T161500Z
LAST-MODIFIED:20210413T173417Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-20
END:VEVENT
BEGIN:VEVENT
UID:0a16fda7-0088-486c-92b7-10c77c04afae
DTSTAMP:20210417T030118Z
CREATED:20201211T183110Z
DESCRIPTION:Topic: Pandora's Box with Correlations: Learning and Approximat
ion\n\nSpeakers: Shuchi Chawla\n\nAffiliation: University of Wisconsin-Mad
ison\n\nIn the Pandora's Box problem\, the algorithm is provided with a nu
mber\nof boxes with unknown (stochastic) rewards contained inside them. Th
e\nalgorithm can open any box at some cost\, discover the reward inside\,
\nand based on these observations can choose one box and keep the reward\n
contained in it. Given the distributions from which the rewards are\ndrawn
\, the algorithm must determine an order in which to open the\nboxes as we
ll as when to stop and accept the best reward found so far.\nIn general\,
an optimal algorithm may make both decisions adaptively\nbased on instanti
ations observed previously. The Pandora's Box problem\nand its extensions
capture many kinds of optimization problems with\nstochastic input where t
he algorithm can obtain instantiations of\ninput random variables at some
cost. Previous work on these problems\nassumes that different random varia
bles in the input are distributed\nindependently. As such it does not capt
ure many real-world settings.\nIn this work\, we provide the first algorit
hms for Pandora's Box-type\nproblems with correlations. In the independent
setting\, optimal\nalgorithms are non-adaptive and based on the notion of
the Gittins\nindex. These techniques fail to extend to the correlated cas
e. We\nassume that the algorithm has access to samples drawn from the join
t\ndistribution on input and provide solutions that require few samples\;
\nare computationally efficient\; and guarantee approximate optimality.\n
\nThis is joint work with Evangelia Gergatsouli\, Yifeng Teng\, Christos\n
Tzamos\, and Ruimin Zhang.\n
DTSTART:20210405T151500Z
DTEND:20210405T161500Z
LAST-MODIFIED:20210405T144311Z
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-481
END:VEVENT
BEGIN:VEVENT
UID:b882a214-6cee-4bcd-a08f-b58a3d5fa350
DTSTAMP:20210417T030118Z
CREATED:20201211T184029Z
DESCRIPTION:Topic: How difficult is it to certify that a random 3SAT formul
a is unsatisfiable?\n\nSpeakers: Toniann Pitassi\n\nAffiliation: Member\,
School of Mathematics\n\nThe Satisfiability problem is perhaps the most fa
mous problem in\ntheoretical computer science\, and significant effort has
been devoted\nto understanding randomly generated SAT instances. The rand
om k-SAT\nmodel (where a random k-CNF formula is chosen by uniformly selec
ting m\nclauses from the set of all possible clauses on k distinct variabl
es)\nis important for several reasons. First\, it is an intrinsically\nnat
ural model analogous to random graph models\, and closely related to\nphas
e transitions and structural phenomena occurring in statistical\nphysics.
Thus like random graph models\, understanding the complexity\nof random SA
T sheds light on fundamental structural properties of the\nsatisfiability
problem. Secondly\, the random k-SAT distribution gives\nus a testbench of
empirically hard examples which are useful for\ncomparing and analyzing S
AT algorithms. Third\, the difficulty of\ncertifying the unsatisfiability
of a random k-SAT formula is connected\nto several other central questions
in complexity theory\, including the\ncomplexity of approximately solving
NP-hard problems\, and the\ncomplexity of learning DNF formulas.\n\nWe wi
ll first review the fascinating world of random structured\ndistributions
(k-SAT\, k-CSP and random graph models)\, their threshold\nproperties\, em
pirical and theoretical results and conjectures about\ntheir complexity an
d structural properties. We then focus on the\nfollowing question: how dif
ficult is it to certify that a given random\nk-SAT formula is unsatisfiabl
e (for a given proof system)? The current\nstate of affairs is perplexing.
On the one hand\, Chvatal and Szemeredi\nfamously proved exponential lowe
r bounds for Resolution refutations of\nrandom k-SAT\, and more recently s
imilar exponential lower bounds have\nbeen shown for SOS (Sum-of-Squares)
and Cutting Planes refutations.\nTaken together these lower bounds prove t
hat most state-of-the-art\nalgorithms will require exponential-time on ran
dom k-SAT instances. On\nthe other hand\, current algorithms are unreasona
bly effective at\nsolving random k-SAT instances! We will sketch the lower
bound proofs\nfor Resolution and the recent lower bound for Cutting Plane
s\nrefutations for random formulas\, and discuss the interesting web of\nc
onnections between the sunflower lemma in extremal combinatorics\,\nthresh
old properties of random structures\, proof complexity lower\nbounds\, and
circuit lower bounds. \n
DTSTART:20210406T143000Z
DTEND:20210406T163000Z
LAST-MODIFIED:20210406T123111Z
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-476
END:VEVENT
BEGIN:VEVENT
UID:162a2bb6-52e0-4af6-b9a9-4cdc1236e215
DTSTAMP:20210417T030118Z
CREATED:20210105T233304Z
DESCRIPTION:Topic: Approximations of infinite groups\n\nSpeakers: Goulnara
Arzhantseva \n\nAffiliation: Universität Wien\n\nWe discuss various (still
open) questions on approximations of\nfinitely generated groups\, focusin
g on finite-dimensional\napproximations such as residual finiteness and so
ficity. We survey our\nresults on the existence\, stability and quantifica
tion of metric\napproximations. We suggest a few conjectures\, e.g. on Gro
mov\nhyperbolic groups and their infinite monster limits.\n\nBased on join
t works with Liviu Paunescu (Bucharest).\n
DTSTART:20210407T150000Z
DTEND:20210407T161500Z
LAST-MODIFIED:20210407T131255Z
LOCATION:Remote Access
SUMMARY:Stability and Testability
URL:https://www.ias.edu/math/events/stability-and-testability-21
END:VEVENT
BEGIN:VEVENT
UID:c34e1d62-3c1f-4c67-9206-dc528d9f2450
DTSTAMP:20210417T030118Z
CREATED:20201211T183141Z
DESCRIPTION:Topic: Privacy as Stability\, for Generalization \n\nSpeakers:
Katrina Legitt\n\nAffiliation: Hebrew University\n\nMany data analysis pip
elines are adaptive: the choice of which\nanalysis to run next depends on
the outcome of previous analyses.\nCommon examples include variable select
ion for regression problems and\nhyper-parameter optimization in large-sca
le machine learning problems:\nin both cases\, common practice involves re
peatedly evaluating a series\nof models on the same dataset. Unfortunately
\, this kind of adaptive\nre-use of data invalidates many traditional meth
ods of avoiding\noverfitting and false discovery\, and has been blamed in
part for the\nrecent flood of non-reproducible findings in the empirical s
ciences.\nAn exciting line of work beginning with Dwork et al. in 2015\nes
tablishes the first formal model and first algorithmic results\nproviding
a general approach to mitigating the harms of adaptivity\,\nvia a connecti
on to the notion of differential privacy.\n\nIn this talk\, we'll explore
the notion of differential privacy and\ngain some understanding of how and
why it provides protection against\nadaptivity-driven overfitting. Many i
nteresting questions in this\nspace remain open.\n\nJoint work with: Chris
topher Jung (UPenn)\, Seth Neel (Harvard)\, Aaron\nRoth (UPenn)\, Saeed Sh
arifi-Malvajerdi (UPenn)\, and Moshe Shenfeld\n(HUJI). This talk will draw
on work that appeared at NeurIPS 2019 and\nITCS 2020.\n
DTSTART:20210412T151500Z
DTEND:20210412T161500Z
LAST-MODIFIED:20210412T115352Z
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
BEGIN:VEVENT
UID:11e83d06-897e-446f-a1f8-8a9a0d6b3dcc
DTSTAMP:20210417T030118Z
CREATED:20210311T133758Z
DESCRIPTION:Topic: On Chen’s recent breakthrough on the Kannan-Lovasz-Simon
ovits conjecture and Bourgain's slicing problem\n\nSpeakers: Ronen Eldan\n
\nAffiliation: Weizmann Institute of Science\n\nIn the mid 80's\, Bourgain
asked the following question: Is there a\nuniversal constant $c>0$ such t
hat every compact convex set $K$ in\n$R^n$\, of unit volume\, must contain
a slice (namely\, a set of the form\n$K \cap H$ for some affine hyperplan
e $H$) whose surface area is at\nleast $c$? \n\nDue to its numerous impli
cations and simple-to-state formulation\, this\nquestion has become one of
the central conjectures of convex geometry.\nTen years later\, Kannan-Lov
asz and Simonovits proposed a related\nquestion\, considering the followin
g isoperimetric problem on\nhigh-dimensional convex bodies: Given a convex
body $K$\, consider the\noptimal way to partition it into two pieces of e
qual volume so as to\nminimize their interface. Is it true that up to a un
iversal constant\,\nthe minimal partition is attained via a hyperplane cut
? This question\nhas a direct implication on the complexity of many comput
ational\nproblems on convex sets and\, moreover\, it was shown to imply\nB
ourgain's slicing conjecture. \n\nVery recently\, Yuansi Chen obtained a s
triking breakthrough\, nearly\nsolving these two problems. In these two ta
lks we aim to give an\noverview on the subject and\, hopefully\, a self co
ntained proof of\nChen's results. On the way towards the result\, we will
become familiar\nwith the concept of 'localization' (a very useful tool to
prove\nconcentration inequalities) and its extension\, stochastic\nlocali
zation\, the main technique used in the proof.\n\n This work is also surve
yed in the recent quanta article:\nhttps://www.quantamagazine.org/statisti
cs-postdoc-tames-decades-old-geometry-problem-20210301/\n
DTSTART:20210420T143000Z
DTEND:20210420T163000Z
LAST-MODIFIED:20210408T200636Z
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-477
END:VEVENT
BEGIN:VEVENT
UID:3e622cbd-abc6-4d5e-a4ad-68a27bfdb053
DTSTAMP:20210417T030118Z
CREATED:20210311T134037Z
DESCRIPTION:Topic: On Chen’s recent breakthrough on the Kannan-Lovasz-Simon
ovits conjecture and Bourgain's slicing problem - Part II\n\nSpeakers: Ron
en Eldan\n\nAffiliation: Weizmann Institute of Science\n\nIn the mid 80's\
, Bourgain asked the following question: Is there a\nuniversal constant $c
>0$ such that every compact convex set $K$ in\n$R^n$\, of unit volume\, mu
st contain a slice (namely\, a set of the form\n$K \cap H$ for some affine
hyperplane $H$) whose surface area is at\nleast $c$? \n\nDue to its nume
rous implications and simple-to-state formulation\, this\nquestion has bec
ome one of the central conjectures of convex geometry.\nTen years later\,
Kannan-Lovasz and Simonovits proposed a related\nquestion\, considering th
e following isoperimetric problem on\nhigh-dimensional convex bodies: Give
n a convex body $K$\, consider the\noptimal way to partition it into two p
ieces of equal volume so as to\nminimize their interface. Is it true that
up to a universal constant\,\nthe minimal partition is attained via a hype
rplane cut? This question\nhas a direct implication on the complexity of m
any computational\nproblems on convex sets and\, moreover\, it was shown t
o imply\nBourgain's slicing conjecture. \n\nVery recently\, Yuansi Chen ob
tained a striking breakthrough\, nearly\nsolving these two problems. In th
ese two talks we aim to give an\noverview on the subject and\, hopefully\,
a self contained proof of\nChen's results. On the way towards the result\
, we will become familiar\nwith the concept of 'localization' (a very usef
ul tool to prove\nconcentration inequalities) and its extension\, stochast
ic\nlocalization\, the main technique used in the proof.\n\n This work is
also surveyed in the recent quanta article:\nhttps://www.quantamagazine.or
g/statistics-postdoc-tames-decades-old-geometry-problem-20210301/\n
DTSTART:20210427T143000Z
DTEND:20210427T163000Z
LAST-MODIFIED:20210408T200558Z
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-478
END:VEVENT
END:VCALENDAR