BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Mehtaab Sawhney (MIT)
DTSTART;VALUE=DATE-TIME:20210930T213000Z
DTEND;VALUE=DATE-TIME:20210930T230000Z
DTSTAMP;VALUE=DATE-TIME:20211209T072812Z
UID:SPAMS/1
DESCRIPTION:Title: ON
LINE VECTOR BALANCING\nby Mehtaab Sawhney (MIT) as part of MIT Simple
Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in t
he Simons Building.\n\nAbstract\nWe study discrepancy minimization for vec
tors in $mb{R}^n$ in\nan online setting. The main result is a pair of near
ly-linear time\nonline algorithms which maintain logarithmic bounds for th
e\nKoml'{o}s~conjecture. The first algorithm is based on a high-dimensiona
l\ncomparison argument while the second is based on a discrete random walk
\non the real line with the Gaussian distribution as a stationary\ndistrib
ution. (Joint w/ Ryan Alweiss\, Yang P. Liu\, Ashwin Sah)\n
LOCATION:https://researchseminars.org/talk/SPAMS/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aaron Berger (MIT)
DTSTART;VALUE=DATE-TIME:20211007T213000Z
DTEND;VALUE=DATE-TIME:20211007T230000Z
DTSTAMP;VALUE=DATE-TIME:20211209T072812Z
UID:SPAMS/2
DESCRIPTION:Title: Re
al Roots of Random Polynomials\nby Aaron Berger (MIT) as part of MIT S
imple Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 - 13
2 in the Simons Building.\n\nAbstract\nHow many real roots does a random p
olynomial of degree n have? By the fundamental theorem of algebra\, it can
have at most n\, but in expectation the answer is often much lower. We'll
attack this problem with just a single algebraic tool (Descartes' law of
signs) and a modest helping of some probabilistic combinatorics.\n
LOCATION:https://researchseminars.org/talk/SPAMS/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chen Lu (MIT Mathematics)
DTSTART;VALUE=DATE-TIME:20211014T213000Z
DTEND;VALUE=DATE-TIME:20211014T230000Z
DTSTAMP;VALUE=DATE-TIME:20211209T072812Z
UID:SPAMS/3
DESCRIPTION:Title: Sa
mpling lower bounds\nby Chen Lu (MIT Mathematics) as part of MIT Simpl
e Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in
the Simons Building.\n\nAbstract\nWe will discuss the following problem:
what is the smallest number of queries we need to make to a target distrib
ution in order to sample from it? We will present some progress towards th
is problem (based on joint work w/ Sinho Chewi\, Patrik Gerber\, Thibaut L
e Gouic\, and Philippe Rigollet).\n
LOCATION:https://researchseminars.org/talk/SPAMS/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:William Kuszmaul (MIT Mathematics)
DTSTART;VALUE=DATE-TIME:20211028T213000Z
DTEND;VALUE=DATE-TIME:20211028T230000Z
DTSTAMP;VALUE=DATE-TIME:20211209T072812Z
UID:SPAMS/4
DESCRIPTION:Title: Li
near Probing Revisited: Tombstones Mark the Demise of Primary Clustering\nby William Kuszmaul (MIT Mathematics) as part of MIT Simple Person's A
pplied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons
Building.\n\nAbstract\nThe linear-probing hash table is one of the oldest
and most widely used data structures in computer science. However\, linear
probing also famously comes with a major drawback: as soon as the hash ta
ble reaches a high memory utilization\, elements within the hash table beg
in to cluster together\, causing insertions to become slow. This phenomeno
n\, now known as "primary clustering"\, was first captured by Donald Knuth
in 1963\; at a load factor of $1 - 1/x$\, the expected time per insertion
becomes $\\Theta(x^2)$\, rather than the more desirable $\\Theta(x)$.\n\n
We show that there is more to the story than the classic analysis would se
em to suggest. It turns out that small design decisions in how deletions a
re implemented have dramatic effects on the asymptotic performance of inse
rtions. If these design decisions are made correctly\, then even a hash ta
ble that is continuously at a load factor $1 - \\Theta(1/x)$ can achieve a
verage insertion time $\\tilde{O}(x)$. A key insight is that the tombstone
s left behind by deletions cause a surprisingly strong "anti-clustering" e
ffect\, and that when insertions and deletions are one-for-one\, the anti-
clustering effects of deletions actually overpower the clustering effects
of insertions.\n\nBased on joint work with Michael A. Bender and Bradley C
. Kuszmaul.\nhttps://arxiv.org/abs/2107.01250\nTo appear in FOCS 2021.\n
LOCATION:https://researchseminars.org/talk/SPAMS/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Nicoletti (MIT Mathematics)
DTSTART;VALUE=DATE-TIME:20211104T213000Z
DTEND;VALUE=DATE-TIME:20211104T230000Z
DTSTAMP;VALUE=DATE-TIME:20211209T072812Z
UID:SPAMS/5
DESCRIPTION:Title: Hy
drodynamic limit for a surface growth model\nby Matthew Nicoletti (MIT
Mathematics) as part of MIT Simple Person's Applied Mathematics Seminar\n
\nLecture held in Room: 2 - 132 in the Simons Building.\n\nAbstract\nWheth
er random or deterministic\, models for surface growth are studied in many
areas of pure and applied math\, and are crucial for understanding natura
l phenomena. We construct and study the basic properties of a surface grow
th model in 2+1 dimensions.\n
LOCATION:https://researchseminars.org/talk/SPAMS/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Allen Liu (MIT EECS)
DTSTART;VALUE=DATE-TIME:20211118T230000Z
DTEND;VALUE=DATE-TIME:20211119T000000Z
DTSTAMP;VALUE=DATE-TIME:20211209T072812Z
UID:SPAMS/6
DESCRIPTION:Title: Te
nsor Completion Made Practical\nby Allen Liu (MIT EECS) as part of MIT
Simple Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 -
132 in the Simons Building.\n\nAbstract\nTensor completion is a natural hi
gher-order generalization of matrix completion where the goal is to recove
r a low-rank tensor from sparse observations of its entries. Existing algo
rithms are either heuristic without provable guarantees\, based on solving
large semidefinite programs which are impractical to run\, or make strong
assumptions such as requiring the factors to be nearly orthogonal. In thi
s paper we introduce a new variant of alternating minimization\, which in
turn is inspired by understanding how the progress measures that guide con
vergence of alternating minimization in the matrix setting need to be adap
ted to the tensor setting. We show strong provable guarantees\, including
showing that our algorithm converges linearly to the true tensors even whe
n the factors are highly correlated and can be implemented in nearly linea
r time. Moreover our algorithm is also highly practical and we show that w
e can complete third order tensors with a thousand dimensions from observi
ng a tiny fraction of its entries. In contrast\, and somewhat surprisingly
\, we show that the standard version of alternating minimization\, without
our new twist\, can converge at a drastically slower rate in practice.\n
LOCATION:https://researchseminars.org/talk/SPAMS/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mehtaab Sawhney (MIT Mathematics)
DTSTART;VALUE=DATE-TIME:20211202T230000Z
DTEND;VALUE=DATE-TIME:20211203T000000Z
DTSTAMP;VALUE=DATE-TIME:20211209T072812Z
UID:SPAMS/7
DESCRIPTION:Title: On
the Hard Core Model and Enumerating Independent Sets\nby Mehtaab Sawh
ney (MIT Mathematics) as part of MIT Simple Person's Applied Mathematics S
eminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\n\nAbstrac
t\nSeminal results of Weitz (2005) and Sly (2010) prove that one can in po
lynomial time approximately count independent sets in 5-regular graphs but
cannot approximately count independent sets in 6-regular graphs (unless N
P=RP). We discuss these results in the broader context of sampling from th
e hard core model and give a high level idea of the proof of each of these
results.\n
LOCATION:https://researchseminars.org/talk/SPAMS/7/
END:VEVENT
END:VCALENDAR