BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se i
Calcreator 2.29.14//
CALSCALE:GREGORIAN
UID:91e8caef-3447-4e5a-939c-2fcdcba9ab57
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:769b61f4-ae53-4452-aa89-cc2dc522bf21
DTSTAMP:20200123T143819Z
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:33c2372c-0b52-4296-a59a-29d1fe96ea08
DTSTAMP:20200123T143819Z
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:6fd2f5b7-e458-44a5-9c58-235eb2bd9d97
DTSTAMP:20200123T143819Z
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:b0c3698a-9a54-493b-83d3-08df2ed937ec
DTSTAMP:20200123T143819Z
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:224ab486-2866-47a3-8961-8553f6b44524
DTSTAMP:20200123T143819Z
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:5913897d-5231-4be1-bab0-c7eafa41ab59
DTSTAMP:20200123T143819Z
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:94450884-cbd7-41f6-8b46-c46310186392
DTSTAMP:20200123T143819Z
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:2edf9303-187b-4f05-aeb8-2eb443ee45b6
DTSTAMP:20200123T143819Z
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:7728339c-cf6e-4945-9e2a-191e6a43ad81
DTSTAMP:20200123T143819Z
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:aa1d7fd2-cabb-47de-8d51-adbf48b97c9b
DTSTAMP:20200123T143819Z
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:611a5547-043c-4848-9610-01493fd568e2
DTSTAMP:20200123T143819Z
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:c2c1c612-b4cb-48f6-acb7-fac128e4d653
DTSTAMP:20200123T143819Z
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:ecfe6b57-909c-486f-8e36-cc3215fb23cd
DTSTAMP:20200123T143819Z
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- Existence and efficient constructio
n of ‘resistance sparsifiers’ -- very sparse graphs that approximately pre
serve effective resistances between all pairs of vertices of the original
graph- Computing effective resistances of all edges in a graph\, and appro
ximating the number of spanning trees in a graph in the fastest known time
. We utilize these decompositions to prove several new results in graph sp
arsification: And more. This is joint works with Timothy Chu\, Yu Gao\, Ya
ng Liu\, Richard Peng\, Saurabh Sawlani\, Junxing Wang\, and Zejun Yu.
DTSTART:20191209T160000Z
DTEND:20191209T170000Z
LAST-MODIFIED:20191214T004501Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100616
END:VEVENT
BEGIN:VEVENT
UID:e47544c8-4595-434e-92ac-8f784baddf90
DTSTAMP:20200123T143819Z
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:de4597a1-8112-4177-a5c9-c78ed2b3349a
DTSTAMP:20200123T143819Z
CREATED:20190607T201502Z
DESCRIPTION:Topic: Thresholds Versus Fractional Expectation-Thresholds\n\nS
peaker: Keith Frankston\, Rutgers University\n\nVideo: https://video.ias.e
du/csdm/2019/1216-KeithFrankston\n\nGiven an increasing family F in {0\,1}
^n\, its measure according to mu_p increases and often exhibits a threshol
d behavior\, growing quickly as p increases from near 0 to near 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 structures (e
.g. random graphs and hypergraphs)\, with estimation of thresholds for spe
cific properties the subject of some of the most challenging work in the a
rea. In 2006\, Kahn and Kalai conjectured that a natural (and often easy t
o calculate) lower bound q(F) (which we refer to as the “expectation-thres
hold”) for the threshold is in fact never far from its actual value. We pr
ove a fractional version (proposed by Talagrand) of this so called “expect
ation-threshold” conjecture showing that for any increasing family 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 element of F. Thi
s result easily implies several previously difficult results in probabilis
tic combinatorics such as thresholds for perfect hypergraph matchings (Joh
ansson–Kahn–Vu) and bounded-degree spanning trees (Montgomery). Our approa
ch builds on a recent breakthrough of Alweiss\, Lovett\, Wu and Zhang on t
he Erdős–Rado “Sunflower Conjecture.” This is joint work with Jeff Kahn\,
Bhargav Narayanan\, and Jinyoung Park.
DTSTART:20191216T160000Z
DTEND:20191216T170000Z
LAST-MODIFIED:20191216T161502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100621
END:VEVENT
BEGIN:VEVENT
UID:a3999f70-3335-4008-a398-ca1c8ba077b3
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Permutation property testing\n\nSpeaker: Fan Wei\, Membe
r\, School of Mathematics\n\nVideo: https://video.ias.edu/csdm/2019/1217-F
anWei\n\nThe importance of analyzing big data and in particular very large
networks has shown that the traditional notion of a fast algorithm\, one
that runs in polynomial time\, is often insufficient. This is where proper
ty testing comes in\, whose goal is to very quickly distinguish between ob
jects that satisfy a certain property from those that are ε-far from satis
fying that property. It turns out to be closely related to major developme
nts in combinatorics\, number theory\, discrete geometry\, and theoretical
computer science. Some of the most general results in this area give 'con
stant query complexity' algorithms\, which means the amount of information
it looks at is independent of the input size. These results are proved us
ing regularity lemmas or graph limits. Unfortunately\, typically the proof
s come with no explicit bound for the query complexity\, or enormous bound
s\, of tower-type or worse\, as a function of 1/ε\, making them impractica
l. We show by entirely new methods that for permutations\, such general re
sults still hold with query complexity only polynomial in 1/ε. We also pro
ve stronger results for graphs through the study of new metrics.
DTSTART:20191217T153000Z
DTEND:20191217T173000Z
LAST-MODIFIED:20191217T154502Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100751
END:VEVENT
BEGIN:VEVENT
UID:0a7dbca4-c387-4afe-b40b-cccbd87918d3
DTSTAMP:20200123T143819Z
CREATED:20191122T190002Z
DESCRIPTION:Topic: Approximating CSPs on expanding structures\, and applica
tions to codes\n\nSpeaker: Madhur Tulsiani\, Toyota Technological Institut
e at Chicago\n\nI will discuss some recent results showing that the sum-of
-squares SDP hierarchy can be used to find approximately optimal solutions
to k-CSPs\, provided that the instance satisfies certain expansion proper
ties. These properties can be shown to follow from (k-1)-dimensional spect
ral expansion\, but are in fact weaker and also present (for example) in i
nstances where each constraint corresponds to a length-k walk in an expand
ing graph. I will also discuss applications to unique and list decoding of
direct sum and direct product codes.\n\nBased on joint works with Vedat L
evi Alev\, Fernando Granha Jeronimo\, Dylan Quintana and Shashank Shrivast
ava.
DTSTART:20200121T153000Z
DTEND:20200121T173000Z
LAST-MODIFIED:20200121T142608Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/106571
END:VEVENT
BEGIN:VEVENT
UID:22fe690c-a4a4-4955-92ef-dabbc979bc4c
DTSTAMP:20200123T143819Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: Marc Vinyals\, Technion - Is
rael Institute of Technology\n\n
DTSTART:20200127T160000Z
DTEND:20200127T170000Z
LAST-MODIFIED:20200115T155152Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100631
END:VEVENT
BEGIN:VEVENT
UID:2138e7e3-39b9-4b58-a204-de350940e6c8
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: Robert Robere\, Member\, Sch
ool of Mathematics\n\n
DTSTART:20200128T153000Z
DTEND:20200128T173000Z
LAST-MODIFIED:20200109T143634Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100731
END:VEVENT
BEGIN:VEVENT
UID:95fd0810-2c86-4851-85d2-b8709633507d
DTSTAMP:20200123T143819Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: Henry Yuen\, University of T
oronto\n\n
DTSTART:20200203T160000Z
DTEND:20200203T170000Z
LAST-MODIFIED:20200109T191945Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100636
END:VEVENT
BEGIN:VEVENT
UID:71119acf-3dd0-42c3-8a52-ce6bc17d7f44
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Robert Robere\, Member\, School of Mathe
matics\n\n
DTSTART:20200204T153000Z
DTEND:20200204T173000Z
LAST-MODIFIED:20200109T192001Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100726
END:VEVENT
BEGIN:VEVENT
UID:22114196-de59-48a8-9484-7da1f7b613c0
DTSTAMP:20200123T143819Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: Michael Krivelevich\, Tel Av
iv University\n\n
DTSTART:20200210T160000Z
DTEND:20200210T170000Z
LAST-MODIFIED:20200109T192018Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100641
END:VEVENT
BEGIN:VEVENT
UID:6e91a30a-7aa5-4276-9ab0-715e9b04a717
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Dor Minzer\, Member\, School of Mathemat
ics\n\n
DTSTART:20200211T153000Z
DTEND:20200211T173000Z
LAST-MODIFIED:20200109T192033Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100721
END:VEVENT
BEGIN:VEVENT
UID:1aa06084-64c1-4edb-8a88-83cca6e053b8
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Dor Minzer\, Member\, School of Mathemat
ics\n\n
DTSTART:20200218T153000Z
DTEND:20200218T173000Z
LAST-MODIFIED:20200109T192049Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100716
END:VEVENT
BEGIN:VEVENT
UID:593613af-17aa-4f9f-b8cb-d97746c5f206
DTSTAMP:20200123T143819Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: Lijie Chen\, Massachusetts I
nstitute of Technology\n\n
DTSTART:20200224T160000Z
DTEND:20200224T170000Z
LAST-MODIFIED:20200109T192110Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100646
END:VEVENT
BEGIN:VEVENT
UID:da4af893-456c-41c3-bc8e-7815e4a085a2
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: TBA\n\nSpeaker: Visu Makam\, Member\, School of Mathemat
ics\n\n
DTSTART:20200225T153000Z
DTEND:20200225T173000Z
LAST-MODIFIED:20200109T192126Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100711
END:VEVENT
BEGIN:VEVENT
UID:eb09c2e8-72bf-44ce-b791-3e68b499b3b7
DTSTAMP:20200123T143819Z
CREATED:20190607T202005Z
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 poly$(\log (\kappa))$. We also provide evidence that the $n^2$ t
ime per evaluation cannot be improved and thus our running time is optimal
.A bottleneck of previous cutting plane methods is to compute leverage sco
res\, a measure of the relative importance of past constraints.Our result
is achieved by a novel multi-layered data structure for leverage score mai
ntenance\, which is a sophisticated combination of diverse techniques such
as random projection\, batched low-rank update\, inverse maintenance\, po
lynomial interpolation\, and fast rectangular matrix multiplication. Inter
estingly\, our method requires a combination of different fast rectangular
matrix multiplication algorithms. Our algorithm not only works for the cl
assical convex optimization setting\, but also generalizes to convex-conca
ve games. We apply our algorithm to improve the runtimes of many interesti
ng problems\, e.g.\, Linear Arrow-Debreu Markets\, Fisher Markets\, and Wa
lrasian equilibrium.\n\nThis is a joint work with Haotian Jiang\, Yin Tat
Lee\, and Sam Chiu-wai Wong
DTSTART:20200302T160000Z
DTEND:20200302T170000Z
LAST-MODIFIED:20200121T171121Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100651
END:VEVENT
BEGIN:VEVENT
UID:fc40e633-0527-4fc4-882e-7acf1e5911e7
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: Visu Makam\, Member\, School
of Mathematics\n\n
DTSTART:20200303T153000Z
DTEND:20200303T173000Z
LAST-MODIFIED:20200109T192219Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100706
END:VEVENT
BEGIN:VEVENT
UID:0bce4492-93a0-4778-9ab8-da0684d17760
DTSTAMP:20200123T143819Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200309T150000Z
DTEND:20200309T160000Z
LAST-MODIFIED:20200109T192248Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100656
END:VEVENT
BEGIN:VEVENT
UID:55f98ccf-e7bd-44f3-af83-9c19d6ad1742
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200310T143000Z
DTEND:20200310T163000Z
LAST-MODIFIED:20200109T192319Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100701
END:VEVENT
BEGIN:VEVENT
UID:64f673d3-803c-46e2-a348-6c8e14f8c156
DTSTAMP:20200123T143819Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200316T150000Z
DTEND:20200316T160000Z
LAST-MODIFIED:20200109T192342Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100661
END:VEVENT
BEGIN:VEVENT
UID:cac78804-71a2-44e8-87a4-c33dfd8a25ff
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200317T143000Z
DTEND:20200317T163000Z
LAST-MODIFIED:20200109T192405Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100696
END:VEVENT
BEGIN:VEVENT
UID:839aa4e8-3fb1-4fd8-b991-448276887fe2
DTSTAMP:20200123T143819Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200323T150000Z
DTEND:20200323T160000Z
LAST-MODIFIED:20200109T192426Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100666
END:VEVENT
BEGIN:VEVENT
UID:da5c381b-4928-48bd-9b1a-56a74a3c6248
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200324T143000Z
DTEND:20200324T163000Z
LAST-MODIFIED:20200109T192455Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100691
END:VEVENT
BEGIN:VEVENT
UID:e42c582f-9821-4cd6-b7ff-a597168b38bd
DTSTAMP:20200123T143819Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200330T150000Z
DTEND:20200330T160000Z
LAST-MODIFIED:20200109T192516Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100671
END:VEVENT
BEGIN:VEVENT
UID:7946602e-fc9d-4674-b3a3-831648de675d
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200331T143000Z
DTEND:20200331T163000Z
LAST-MODIFIED:20200109T192542Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100686
END:VEVENT
BEGIN:VEVENT
UID:a8ac10c7-98ce-4bfd-893f-0bfe601305b4
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200406T150000Z
DTEND:20200406T160000Z
LAST-MODIFIED:20200109T192605Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100676
END:VEVENT
BEGIN:VEVENT
UID:f33b444b-f3da-4718-98f1-98ac6212387b
DTSTAMP:20200123T143819Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200407T143000Z
DTEND:20200407T163000Z
LAST-MODIFIED:20200109T192626Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100681
END:VEVENT
END:VCALENDAR