BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se i
Calcreator 2.29.14//
CALSCALE:GREGORIAN
UID:6cb3e9c6-9891-4207-ae26-eba744b5eaa2
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:16230c42-e87f-4398-8a9c-81918979d0b0
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: An improved sunflower bound.\n\nSpeaker: Jiapeng Zhang\,
Harvard University\n\nVideo: https://video.ias.edu/csdm/2019/1007-Jiapeng
Zhang\n\nA sunflower with $r$ petals is a collection of $r$ sets so that t
he intersection of each pair is equal to the intersection of all. Erdos an
d Rado in 1960 proved the sunflower lemma: for any fixed $r$\, any family
of sets of size $w$\, with at least about $w^w$ sets\, must contain a sunf
lower. The famous sunflower conjecture is that the bound on the number of
sets can be improved to $c^w$ for some constant $c$. Despite much research
\, the best bounds until recently were all of the order of $w^{cw}$ for so
me constant c. In this work\, we improve the bounds to about $(log w)^w$.
Joint work with Ryan Alweiss\, Shachar Lovett and Kewen Wu.
DTSTART:20191007T150000Z
DTEND:20191007T160000Z
LAST-MODIFIED:20191007T181502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100571
END:VEVENT
BEGIN:VEVENT
UID:24389999-55ad-49a2-a926-891cf0b93d15
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Asymptotic spectra and Applications I\n\nSpeaker: Jeroen
Zuiddam\, Member\, School of Mathematics\n\nVideo: https://video.ias.edu/
csdm/2019/1008-JeroenZuiddam\n\nThe first lecture in this series is an int
roduction to the theory of asymptotic spectra. This theory describes asymp
totic behavior of basic objects in mathematics like graphs and tensors. Ex
ample applications that we will see are the matrix multiplication problem\
, the cap set problem\, the sunflower problem\, the quantum entanglement p
roblem\, and the problem of efficient communication over a noisy channel.
We will start from scratch.
DTSTART:20191008T143000Z
DTEND:20191008T163000Z
LAST-MODIFIED:20191008T192005Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100801
END:VEVENT
BEGIN:VEVENT
UID:e6672468-4e8f-4667-b966-6ad3c01cee6f
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: Choiceless Polynomial Time\n\nSpeaker: Ben Rossman\, Uni
versity of Toronto\n\nVideo: https://video.ias.edu/csdm/2019/1017-BenRossm
an\n\nThe choiceless computation model of Blass\, Gurevich and Shelah (199
9\, 2002) is an algorithmic framework for computing isomorphism-invariant
properties of unordered structures. Machines in this model have the power
of parallel execution\, but lack the ability to make arbitrary choices. Fo
r example\, a choiceless algorithm cannot freely select an arbitrary neigh
bor of a vertex in an unordered graph\, but may execute a subroutine in pa
rallel over all neighbors. In this talk\, I will give an overview of resul
ts in the choiceless model and discuss the intriguing open question: Does
every graph property that is decidable by a poly-time Turing machine admit
a choiceless poly-time algorithm?
DTSTART:20191014T150000Z
DTEND:20191014T160000Z
LAST-MODIFIED:20191014T144501Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100576
END:VEVENT
BEGIN:VEVENT
UID:c45d6560-7b9d-4282-98bf-d794b54f9d14
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Asymptotic spectra and Applications II\n\nSpeaker: Jeroe
n Zuiddam\, Member\, School of Mathematics\n\nVideo: https://video.ias.edu
/csdm/2019/1015-JeroenZuiddam\n\nIn this second lecture in my series on as
ymptotic spectra we will focus on one application: the matrix multiplicati
on problem. We will use the asymptotic spectrum of tensors to prove that a
very general method (that includes the methods used to obtain the current
ly best algorithms) cannot give faster matrix multiplication algorithms. K
eywords are Shannon entropy\, representation theory and moment polytopes\,
but prior knowledge of these is not assumed.
DTSTART:20191015T143000Z
DTEND:20191015T163000Z
LAST-MODIFIED:20191015T142005Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100796
END:VEVENT
BEGIN:VEVENT
UID:87cac9b1-553f-429a-a544-34ff53b064e9
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: Learning arithmetic circuits in the average case via low
er bounds\n\nSpeaker: Ankit Garg\, Microsoft Research\n\nVideo: https://vi
deo.ias.edu/csdm/2019/1021-AnkitGarg\n\nThe problem of learning arithmetic
circuits is the following: given a polynomial as a black box that is prom
ised to have a small arithmetic circuit computing it\, can we find this ar
ithmetic circuit? This problem is hard in the worst case and so previous w
orks have focused on regimes where the NP-hardness doesn’t kick in (e.g. c
onstant top fan-in etc.). We focus on the average case where one assumes c
ertain non-degeneracy assumptions on the circuit (formally these amount to
assuming the circuit parameters lie outside a certain variety and hence i
f they are chosen randomly according to any reasonable distribution\, the
non-degeneracy condition is satisfied whp). Kayal and Saha gave a meta fra
mework for designing these algorithms for circuit classes where we have lo
wer bounds. They carried this out for depth 3 circuits (sums of products o
f linear forms) and we (in joint work with Kayal and Saha) carry it out fo
r depth 4 powering circuits (sums of powers of low degree polynomials). I
will talk about the meta framework and then about our specific results. I
will also talk about a potential application to learning mixtures of gener
al Gaussians.
DTSTART:20191021T150000Z
DTEND:20191021T160000Z
LAST-MODIFIED:20191021T144502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100581
END:VEVENT
BEGIN:VEVENT
UID:ac0d2116-5cb1-49ed-be10-7bb8237a9098
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Towards a theory of non-commutative optimization: geodes
ic 1st and 2nd order methods for moment maps and polytopes\n\nSpeaker: Raf
ael Oliveira\, University of Toronto\n\nVideo: https://video.ias.edu/csdm/
2019/1022-RafaelOliveira\n\nScaling problems\, such as operator scaling an
d tensor scaling\, have recently found several applications in diverse are
as of math and CS. They have been used to give efficient algorithms for no
n-commutative rational identity testing\, compute the optimal constant in
Brascamp-Lieb inequalities\, one-body quantum marginal problem\, solution
to the Paulsen problem\, and the search version of the Horn's problem\, to
name a few\, [GGOW15\, GGOW18\, BFGOWW18\, KLLR18\, F18]. Scaling problem
s are natural geodesic convex optimization problems on Riemannian manifold
s that arise from the symmetries of non-commutative groups\, and the algor
ithms (and their analyses) developed in these previous works heavily relie
d on this general form of convexity. In this talk we discuss our recent sy
stematic development of a theory of non-commutative optimization\, which g
reatly extends ordinary (Euclidean) convex optimization. We will see how N
C optimization unify and generalize the algorithms developed for the unifo
rm and non-uniform versions of the operator scaling and tensor scaling pro
blems. More specifically\, our algorithms minimize the moment map (a non-c
ommutative notion of the usual gradient)\, and test membership in moment p
olytopes (a vast class of polytopes\, typically of exponential vertex and
facet complexity\, which quite magically arise from this a priori non-conv
ex\, non-linear setting). In the spirit of standard convex optimization\,
we develop two general methods in the geodesic setting\, a first order and
a second order method\, which respectively receive first and second order
information on the derivatives'' of the function to be optimized. We will
also show the key parameters of the underlying group actions which contro
l convergence to the optimum in each of these methods. The non-commutative
analogues of smoothness'' (from the commutative case) are far more comple
x\, and require significant algebraic and analytic machinery (much existin
g and some newly developed in this work). Despite this complexity\, we sha
ll see that the way in which these parameters control convergence in both
methods is quite simple and elegant. Based on joint work with Peter Buergi
sser\, Cole Franks\, Ankit Garg\, Michael Walter and Avi Wigderson.
DTSTART:20191022T143000Z
DTEND:20191022T163000Z
LAST-MODIFIED:20191022T141501Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100791
END:VEVENT
BEGIN:VEVENT
UID:c9e6a807-f852-483d-bf9b-7c0c5c08eb68
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: Furstenberg sets in finite fields\n\nSpeaker: Zeev Dvir\
, Princeton University\n\nVideo: https://video.ias.edu/csdm/2019/1028-Zeev
Dvir\n\nA (k\,m)-Furstenberg set K in F^n\, where F is a finite field\, is
a set such that any k-dimensional subspace of F^n can be shifted so that
it intersects K in at least m points. Such sets generalize in a natural wa
y finite field Kakeya sets (in which k=1\, and m=|F|)\, whose study has re
sulted in many applications\, including in theoretical computer science. T
he main question is how small can such a set K be. While the polynomial me
thod gives a complete answer to this question when k=1 (i.e.\, when K inte
rsects lines in all directions)\, it fails completely for larger values of
k. Until recently\, the only bound for general k and m was given by Ellen
berg and Erman using scheme theoretic techniques. In this talk I will disc
uss a new result (joint with Manik Dhar and Ben Lund) that give improved (
and in some cases tight) upper bounds on the size of Furstenberg sets for
general k and m using completely elementary arguments.
DTSTART:20191028T150000Z
DTEND:20191028T160000Z
LAST-MODIFIED:20191028T141502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100586
END:VEVENT
BEGIN:VEVENT
UID:5e6a1934-f87f-4678-983d-400306b11ea4
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Extremal set theory\n\nSpeaker: Andrey Kupavskii\, Membe
r\, School of Mathematics\n\nVideo: https://video.ias.edu/csdm/2019/1029-A
ndreyKupavskii\n\nExtremal set theory typically asks for the largest colle
ction of sets satisfying certain constraints. In the first talk of these s
eries\, I'll cover some of the classical results and methods in extremal s
et theory. In particular\, I'll cover the recent progress in the Erdos Mat
ching Conjecture\, which suggests the largest size of a family of k-subset
s of an n-element set with no s pairwise disjoint sets.
DTSTART:20191029T143000Z
DTEND:20191029T163000Z
LAST-MODIFIED:20191029T131501Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100786
END:VEVENT
BEGIN:VEVENT
UID:c5b276c7-3bcc-4387-a833-6e4ea2fe40bb
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: Privacy via ill-posedness\n\nSpeaker: Anna Gilbert\, Uni
versity of Michigan\; Member\, School of Mathematics\n\nVideo: https://vid
eo.ias.edu/csdm/2019/1104-AnnaGilbert\n\nIn this work\, we exploit the ill
-posedness of linear inverse\nproblems to design algoithms to release diff
erentially private data or\nmeasurements of the physical system. We discus
s the spectral\nrequirements on a matrix such that only a small amount of
noise is\nneeded to achieve privacy and contrast this with the poor condit
ioning\nof the system. We then instantiate our framework with several\ndif
fusion operators and explore recovery via l1 constrained\nminimisation. Ou
r work indicates that it is possible to produce\nlocally private sensor me
asurements that both keep the exact locations\nof initial heat sources pri
vate and permit recovery of the “general\ngeographic vicinity” of the sour
ces.\n\nJoint work with Audra McMillan
DTSTART:20191104T160000Z
DTEND:20191104T170000Z
LAST-MODIFIED:20191104T171502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100591
END:VEVENT
BEGIN:VEVENT
UID:99805562-0236-4262-bc8d-db78cc576553
DTSTAMP:20191212T090225Z
CREATED:20191101T152004Z
DESCRIPTION:Topic: Extremal set theory\n\nSpeaker: Andrey Kupavskii\, Membe
r\, School of Mathematics\n\nVideo: https://video.ias.edu/csdm/2019/1105-A
ndreyKupavskii\n\nExtremal set theory typically asks for the largest colle
ction of sets satisfying certain constraints. In the first talk of these s
eries\, I'll cover some of the classical results and methods in extremal s
et theory. In particular\, I'll cover the recent progress in the Erdos Mat
ching Conjecture\, which suggests the largest size of a family of k-subset
s of an n-element set with no s pairwise disjoint sets.
DTSTART:20191105T153000Z
DTEND:20191105T173000Z
LAST-MODIFIED:20191105T151502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/106141
END:VEVENT
BEGIN:VEVENT
UID:ff81f083-95c5-468d-bdee-77a83cfd159a
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Speaker: No Seminar\n\n
DTSTART:20191111T160000Z
DTEND:20191111T170000Z
LAST-MODIFIED:20191101T220002Z
LOCATION:No Seminar - FOCS
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100596
END:VEVENT
BEGIN:VEVENT
UID:184b99f9-43ba-4b68-8261-f613ff2c638e
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Speaker: No Seminar\n\n
DTSTART:20191112T153000Z
DTEND:20191112T173000Z
LAST-MODIFIED:20191101T220002Z
LOCATION:No Seminar - FOCS
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100776
END:VEVENT
BEGIN:VEVENT
UID:9426dbf5-47a6-4f2e-9b99-60a53d8f1c6b
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: An isoperimetric inequality for the Hamming cube and som
e consequences\n\nSpeaker: Jinyoung Park\, Rutgers University\n\nVideo: ht
tps://video.ias.edu/csdm/2019/1118-JinyoungPark\n\nI will introduce an iso
perimetric inequality for the Hamming cube and some of its applications. T
he applications include a “stability” version of Harper’s edge-isoperimetr
ic inequality\, which was first proved by Friedgut\, Kalai and Naor for ha
lf cubes\, and later by Ellis for subsets of any size. Our inequality also
plays a key role in a recent result on the asymptotic number of maximal i
ndependent sets in the cube. This is joint work with Jeff Kahn.
DTSTART:20191118T160000Z
DTEND:20191118T170000Z
LAST-MODIFIED:20191118T191502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100601
END:VEVENT
BEGIN:VEVENT
UID:43db0f10-1986-4c59-8be7-25e0cce974f5
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Constraint Satisfaction Problems and Probabilistic Combi
natorics I\n\nSpeaker: Fotios Illiopoulos\, Member\, School of Mathematics
\n\nVideo: https://video.ias.edu/csdm/2019/1119-FotiosIlliopoulos\n\nThe t
asks of finding and randomly sampling solutions of constraint satisfaction
problems over discrete variable sets arise naturally in a wide variety of
areas\, among them artificial intelligence\, bioinformatics and combinato
rics\, and further have deep connections to statistical physics.\n\nIn thi
s first talk of the series\, I'll cover some recent results regarding algo
rithms for finding and sampling solutions of constraint satisfaction probl
ems\, which are inspired by the Lovasz Local Lemma. The latter is a powerf
ul tool in probabilistic combinatorics\, guaranteeing the existence of con
figurations that avoid a collection of 'bad' events that are mostly indepe
ndent and have low probability.
DTSTART:20191119T153000Z
DTEND:20191119T173000Z
LAST-MODIFIED:20191119T174502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100771
END:VEVENT
BEGIN:VEVENT
UID:5e1ceea9-29d6-4feb-aea1-603d7cd917e9
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: Lifting small locally testable codes (LTCs) to large LTC
s via HDXs\n\nSpeaker: Prahladh Harsha\, Tata Institute of Fundamental Res
earch\n\nVideo: https://video.ias.edu/csdm/2019/1125-PrahladhHarsha\n\nIn
this talk\, I'll illustrate how to lift a 'small' locally testable code vi
a a high dimensional expander (HDX) to a 'large' locally testable code. Gi
ven a D-left regular bipartite graph G = ([n]\, [m]\, E) and a 'small' cod
e C \in {0\,1}^D\, the Tanner construction shows how to lift this code to
a 'large' code on n- bits. These Tanner lifts are extremely useful. For in
stance\, if C is a 'small' code with good distance and rate and G is a bip
artite expander\, then the Sipser-Spielman analysis shows that the lifted
code is a 'large' code that has good distance and rate. We will show a sim
ilar lifting property for local-testability. More precisely\, let C_0 be a
small code such that its lift C (defined via a bipartite graph) has non-t
rivial rate. We will show that if the bipartite-graph is part of a HDX and
a small-lift is testable\, then so is the large-lift C.
DTSTART:20191125T160000Z
DTEND:20191125T170000Z
LAST-MODIFIED:20191125T154502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100606
END:VEVENT
BEGIN:VEVENT
UID:94d27049-b57d-4743-8bd2-104e16446e1c
DTSTAMP:20191212T090225Z
CREATED:20190816T181502Z
DESCRIPTION:Topic: Constraint Satisfaction Problems and Probabilistic Combi
natorics II\n\nSpeaker: Fotios Illiopoulos\, Member\, School of Mathematic
s\n\nVideo: https://video.ias.edu/csdm/2019/1126-FotiosIlliopoulos\n\nThe
tasks of finding and randomly sampling solutions of constraint satisfactio
n problems over discrete variable sets arise naturally in a wide variety o
f areas\, among them artificial intelligence\, bioinformatics and combinat
orics\, and further have deep connections to statistical physics.\n\nIn th
is second talk of the series\, I'll cover some results regarding random co
nstraint satisfaction problems and their connection to statistical physics
.
DTSTART:20191126T153000Z
DTEND:20191126T173000Z
LAST-MODIFIED:20191126T151502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/102986
END:VEVENT
BEGIN:VEVENT
UID:cf934caa-40ca-4319-9cf9-b9452e7c3875
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: Rainbow fractional matchings\n\nSpeaker: Ron Holzman\, T
echnion\n\nVideo: https://video.ias.edu/csdm/2019/1202-RonHolzman\n\nGiven
a family of m matchings in a graph G (where each matching can be thought
of as a color class)\, a rainbow matching is a choice of edges of distinct
colors that forms a matching. How many matchings of size n are needed to
guarantee the existence of a rainbow matching of size n? If G is bipartite
\, a theorem of Drisko generalized by Aharoni and Berger says that m = 2n
- 1 suffices (and is best possible). In a general graph G\, this is not th
e case\, but m = 2n is conjectured to be enough. We prove a fractional ver
sion of this conjecture\, not only for graphs but also for r-uniform hyper
graphs. The main tool is a topological result of Kalai and Meshulam. This
is joint work with Ron Aharoni and Zilin Jiang.
DTSTART:20191202T160000Z
DTEND:20191202T170000Z
LAST-MODIFIED:20191202T153002Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100611
END:VEVENT
BEGIN:VEVENT
UID:379a230f-34cb-401a-afdf-8d8148e22166
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Regularity lemma and its applications Part I\n\nSpeaker:
Fan Wei\, Member\, School of Mathematics\n\nSzemeredi's regularity lemma
is an important tool in modern graph theory. It and its variants have nume
rous applications in graph theory\, which in turn has applications in fiel
ds such as theoretical computer science and number theory. The first part
of the talk covers some basic knowledge about the regularity lemma and som
e of its applications\, such as the graph removal lemma. I will also discu
ss some recent works related to the removal lemma.
DTSTART:20191203T153000Z
DTEND:20191203T173000Z
LAST-MODIFIED:20191203T142004Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100761
END:VEVENT
BEGIN:VEVENT
UID:c6d369ff-8707-468b-a20e-d27582516993
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: Graph Sparsification via Short Cycle Decomposition\n\nSp
eaker: Sushant Sachdeva\, University of Toronto\; Member\, School of Mathe
matics\n\nVideo: https://video.ias.edu/csdm/2019/1209-SushantSachdeva\n\nW
e develop a framework for graph sparsification and sketching\, based on a
new tool\, short cycle decomposition -- a decomposition of an unweighted g
raph into an edge-disjoint collection of short cycles\, plus a small numbe
r of extra edges. A simple observation gives that every graph G on n verti
ces with m edges can be decomposed in O(mn) time into cycles of length at
most 2 log n\, and at most 2n extra edges. We give an almost-linear time a
lgorithm for constructing a short cycle decomposition\, with sub-polynomia
l n^o(1) cycle length\, and almost-linear number of extra edges. - Existen
ce and efficient construction of a spectral sparsifier of a graph that exa
ctly preserve original vertex degrees\n- Existence and efficient construct
ion of ‘resistance sparsifiers’ -- very sparse graphs that approximately p
reserve effective resistances between all pairs of vertices of the origina
l graph\n- Computing effective resistances of all edges in a graph\, and a
pproximating the number of spanning trees in a graph in the fastest known
time. We utilize these decompositions to prove several new results in grap
h sparsification: And more. This is joint works with Timothy Chu\, Yu Gao\
, Yang Liu\, Richard Peng\, Saurabh Sawlani\, Junxing Wang\, and Zejun Yu.
DTSTART:20191209T160000Z
DTEND:20191209T170000Z
LAST-MODIFIED:20191212T003001Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100616
END:VEVENT
BEGIN:VEVENT
UID:5c73eb91-9172-4e66-a435-2efa3ef024cb
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Graph removal lemmas\n\nSpeaker: Fan Wei\, Member\, Scho
ol of Mathematics\n\nContinuing last week's lecture\, among the numerous a
pplications of the regularity lemma\, a classical one is the graph removal
lemma. It has applications in fields such as number theory and theoretica
l computer science. For every fixed graph H\, the H-removal lemma gives a
highly nontrivial equivalence between the density of H in G and the L1 dis
tance between a graph G to the set of H-free graphs. The quantitative esti
mates remains a big open question in graph theory. In this talk\, I will c
over the standard proof of the graph removal lemma\, and discuss some rece
nt works on a strengthening of the usual graph removal lemma.
DTSTART:20191210T153000Z
DTEND:20191210T173000Z
LAST-MODIFIED:20191204T150002Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100756
END:VEVENT
BEGIN:VEVENT
UID:ed43dfad-76bf-426e-820a-9f82f88d4ea4
DTSTAMP:20191212T090225Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: Thresholds Versus Fractional Expectation-Thresholds\n\nS
peaker: Keith Frankston\, Rutgers University\n\nGiven an increasing family
F in {0\,1}^n\, its measure according to mu_p increases and often exhibit
s a threshold behavior\, growing quickly as p increases from near 0 to nea
r 1 around a specific value p_c. Thresholds of families have been of great
historical interest and a central focus of the study of random discrete s
tructures (e.g. random graphs and hypergraphs)\, with estimation of thresh
olds for specific properties the subject of some of the most challenging w
ork in the area. In 2006\, Kahn and Kalai conjectured that a natural (and
often easy to calculate) lower bound q(F) (which we refer to as the “expec
tation-threshold”) for the threshold is in fact never far from its actual
value. We prove a fractional version (proposed by Talagrand) of this so ca
lled “expectation-threshold” conjecture showing that for any increasing fa
mily we have p_c(F) = O(q_f(F) log \ell(F))\, where q_f is the “fractional
expectation-threshold” and \ell(F) is the maximum size of a minimal eleme
nt of F. This result easily implies several previously difficult results i
n probabilistic combinatorics such as thresholds for perfect hypergraph ma
tchings (Johansson–Kahn–Vu) and bounded-degree spanning trees (Montgomery)
. Our approach builds on a recent breakthrough of Alweiss\, Lovett\, Wu an
d Zhang on the Erdős–Rado “Sunflower Conjecture.” This is joint work with
Jeff Kahn\, Bhargav Narayanan\, and Jinyoung Park.
DTSTART:20191216T160000Z
DTEND:20191216T170000Z
LAST-MODIFIED:20191206T183002Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100621
END:VEVENT
BEGIN:VEVENT
UID:550fd30a-a817-477c-a25b-419670414c87
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Robert Robere\, Member\, School of Mathe
matics\n\n
DTSTART:20191217T153000Z
DTEND:20191217T173000Z
LAST-MODIFIED:20191122T181502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100751
END:VEVENT
BEGIN:VEVENT
UID:35a8be7d-568f-4f44-a186-7c48c2951fd5
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: An Improved Cutting Plane Method for Convex Optimization
\, Convex-Concave Games and its Applications\n\nSpeaker: Zhao Song\, Membe
r\, School of Mathematics\n\nGiven a separation oracle for a convex set $K
\subset \mathbb{R}^n$ that is contained in a box of radius $R$\, the goal
is to either compute a point in $K$ or prove that $K$ does not contain a
ball of radius $\epsilon$. We propose a new cutting plane algorithm that u
ses an optimal $O(n \log (\kappa))$ evaluations of the oracle and an addit
ional $O(n^2)$ time per evaluation\, where $\kappa = nR/\epsilon$.\n\n- Th
is improves upon Vaidya's $O( \text{SO} \cdot n \log (\kappa) + n^{\omega+
1} \log (\kappa))$ time algorithm [Vaidya\, FOCS 1989a] in terms of polyno
mial dependence on $n$\, where $\omega\n- This improves upon Lee-Sidford-W
ong's $O( \text{SO} \cdot n \log (\kappa) + n^3 \log^{O(1)} (\kappa))$ tim
e algorithm [Lee\, Sidford and Wong\, FOCS 2015] in terms of dependence on
$\kappa$.\n\nFor many important applications in economics\, $\kappa = \Om
ega(\exp(n))$ and this leads to a significant difference between $\log(\ka
ppa)$ and $\text{poly}(\log (\kappa))$. We also provide evidence that the
$n^2$ time per evaluation cannot be improved and thus our running time is
optimal. A bottleneck of previous cutting plane methods is to compute leve
rage scores\, a measure of the relative importance of past constraints. Ou
r result is achieved by a novel multi-layered data structure for leverage
score maintenance\, which is a sophisticated combination of diverse techni
ques such as random projection\, batched low-rank update\, inverse mainten
ance\, polynomial interpolation\, and fast rectangular matrix multiplicati
on. Interestingly\, our method requires a combination of different fast re
ctangular matrix multiplication algorithms. Our algorithm not only works f
or the classical convex optimization setting\, but also generalizes to con
vex-concave games. We apply our algorithm to improve the runtimes of many
interesting problems\, e.g.\, Linear Arrow-Debreu Markets\, Fisher Markets
\, and Walrasian equilibrium.This is a joint work with Haotian Jiang\, Yin
Tat Lee\, and Sam Chiu-wai Wong.
DTSTART:20200114T153000Z
DTEND:20200114T173000Z
LAST-MODIFIED:20191211T193001Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100741
END:VEVENT
BEGIN:VEVENT
UID:16a50543-4dbe-42a4-b55d-9366b4a13639
DTSTAMP:20191212T090225Z
CREATED:20191122T190002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Madhur Tulsiani\, Toyota Technological I
nstitute at Chicago\n\n
DTSTART:20200121T153000Z
DTEND:20200121T173000Z
LAST-MODIFIED:20191206T184502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/106571
END:VEVENT
BEGIN:VEVENT
UID:fdec457b-8e2c-4563-b3ba-530e5325cdea
DTSTAMP:20191212T090225Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200127T160000Z
DTEND:20200127T170000Z
LAST-MODIFIED:20190607T202005Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100631
END:VEVENT
BEGIN:VEVENT
UID:aa7ce402-a120-43b0-b43f-fc4cf6d7d6df
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Robert Robere\, Member\, School of Mathe
matics\n\n
DTSTART:20200128T153000Z
DTEND:20200128T173000Z
LAST-MODIFIED:20191206T184502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100731
END:VEVENT
BEGIN:VEVENT
UID:ed39f963-898c-46d7-b55e-52f5db023687
DTSTAMP:20191212T090225Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200203T160000Z
DTEND:20200203T170000Z
LAST-MODIFIED:20190607T202005Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100636
END:VEVENT
BEGIN:VEVENT
UID:6aeb964a-bf84-48e5-9f3e-e72e4440557c
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Robert Robere\, Member\, School of Mathe
matics\n\n
DTSTART:20200204T153000Z
DTEND:20200204T173000Z
LAST-MODIFIED:20191206T184502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100726
END:VEVENT
BEGIN:VEVENT
UID:791300dc-36ce-44e5-b47f-53c69ded72e3
DTSTAMP:20191212T090225Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200210T160000Z
DTEND:20200210T170000Z
LAST-MODIFIED:20190607T202005Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100641
END:VEVENT
BEGIN:VEVENT
UID:ebed0737-3643-44e1-9ba4-b50db086e60e
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Dor Minzer\, Member\, School of Mathemat
ics\n\n
DTSTART:20200211T153000Z
DTEND:20200211T173000Z
LAST-MODIFIED:20191206T183002Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100721
END:VEVENT
BEGIN:VEVENT
UID:841c192d-ac42-4a1b-b7f8-4d490f79a184
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Dor Minzer\, Member\, School of Mathemat
ics\n\n
DTSTART:20200218T153000Z
DTEND:20200218T173000Z
LAST-MODIFIED:20191206T183002Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100716
END:VEVENT
BEGIN:VEVENT
UID:d2872494-18f1-42b5-8c86-e8fd505b7615
DTSTAMP:20191212T090225Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Lijie Chen\n\n
DTSTART:20200224T160000Z
DTEND:20200224T170000Z
LAST-MODIFIED:20191204T193001Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100646
END:VEVENT
BEGIN:VEVENT
UID:c00974ff-0506-4126-af50-f3d340895b42
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Visu Makam\, Member\, School of Mathemat
ics\n\n
DTSTART:20200225T153000Z
DTEND:20200225T173000Z
LAST-MODIFIED:20191204T193001Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100711
END:VEVENT
BEGIN:VEVENT
UID:6376c495-e7d2-4dc7-9831-f9388b9effb5
DTSTAMP:20191212T090225Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200302T160000Z
DTEND:20200302T170000Z
LAST-MODIFIED:20190607T202005Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100651
END:VEVENT
BEGIN:VEVENT
UID:013f5bc3-fcab-448f-8212-9110ece6c1ee
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Visu Makam\, Member\, School of Mathemat
ics\n\n
DTSTART:20200303T153000Z
DTEND:20200303T173000Z
LAST-MODIFIED:20191206T183002Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100706
END:VEVENT
BEGIN:VEVENT
UID:fcb30b50-44f1-4190-9b90-7ca2e6719359
DTSTAMP:20191212T090225Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200309T150000Z
DTEND:20200309T160000Z
LAST-MODIFIED:20190607T202005Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100656
END:VEVENT
BEGIN:VEVENT
UID:7a88fa80-b883-4ad3-8f04-87d573d1ce02
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200310T143000Z
DTEND:20200310T163000Z
LAST-MODIFIED:20191101T161501Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100701
END:VEVENT
BEGIN:VEVENT
UID:f75e4caa-c71b-418b-8573-1688514b0c8e
DTSTAMP:20191212T090225Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200316T150000Z
DTEND:20200316T160000Z
LAST-MODIFIED:20190607T202005Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100661
END:VEVENT
BEGIN:VEVENT
UID:ba110e5b-4453-4131-88a9-1b5700b26c2b
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200317T143000Z
DTEND:20200317T163000Z
LAST-MODIFIED:20191101T161501Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100696
END:VEVENT
BEGIN:VEVENT
UID:c059a8d5-1b69-4d41-b0f8-cd042024063f
DTSTAMP:20191212T090225Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200323T150000Z
DTEND:20200323T160000Z
LAST-MODIFIED:20190607T202005Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100666
END:VEVENT
BEGIN:VEVENT
UID:63e0bd67-da09-48e4-9d19-476c0fba155c
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200324T143000Z
DTEND:20200324T163000Z
LAST-MODIFIED:20191101T161501Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100691
END:VEVENT
BEGIN:VEVENT
UID:9f674541-dc03-496c-af0f-49963fe7f5e4
DTSTAMP:20191212T090225Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200330T150000Z
DTEND:20200330T160000Z
LAST-MODIFIED:20190607T202005Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100671
END:VEVENT
BEGIN:VEVENT
UID:f6c2b4d7-5936-417b-ac52-422435b7c709
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200331T143000Z
DTEND:20200331T163000Z
LAST-MODIFIED:20191101T161501Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100686
END:VEVENT
BEGIN:VEVENT
UID:c4b033a1-ee4d-4c6d-b37c-88d5f015b9ee
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200406T150000Z
DTEND:20200406T160000Z
LAST-MODIFIED:20190607T203002Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100676
END:VEVENT
BEGIN:VEVENT
UID:c8afdb27-3f07-4ded-a902-6f213839adb9
DTSTAMP:20191212T090225Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: TBA\n\n
DTSTART:20200407T143000Z
DTEND:20200407T163000Z
LAST-MODIFIED:20191101T161501Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100681
END:VEVENT
END:VCALENDAR