BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Mehtaab Sawhney (MIT) DTSTART:20210930T213000Z DTEND:20210930T230000Z DTSTAMP:20260422T212554Z 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:20211007T213000Z DTEND:20211007T230000Z DTSTAMP:20260422T212554Z 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:20211014T213000Z DTEND:20211014T230000Z DTSTAMP:20260422T212554Z 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:20211028T213000Z DTEND:20211028T230000Z DTSTAMP:20260422T212554Z 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:20211104T213000Z DTEND:20211104T230000Z DTSTAMP:20260422T212554Z 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:20211118T230000Z DTEND:20211119T000000Z DTSTAMP:20260422T212554Z 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:20211202T230000Z DTEND:20211203T000000Z DTSTAMP:20260422T212554Z 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 BEGIN:VEVENT SUMMARY:Jonathan Tidor (MIT) DTSTART:20220210T223000Z DTEND:20220211T000000Z DTSTAMP:20260422T212554Z UID:SPAMS/8 DESCRIPTION:Title: Co mmunication complexity\nby Jonathan Tidor (MIT) as part of MIT Simple Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in t he Simons Building.\nAbstract: TBA\n LOCATION:https://researchseminars.org/talk/SPAMS/8/ END:VEVENT BEGIN:VEVENT SUMMARY:Guanghao Ye (MIT) DTSTART:20220217T223000Z DTEND:20220218T000000Z DTSTAMP:20260422T212554Z UID:SPAMS/9 DESCRIPTION:Title: Ne sted Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time \nby Guanghao Ye (MIT) as part of MIT Simple Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\n\nAbstra ct\nWe present a nearly-linear time algorithm for finding a minimum-cost f low in planar graphs with polynomially bounded integer costs and capacitie s. The previous fastest algorithm for this problem is based on interior-po int methods (IPMs) and works for general sparse graphs in $O(n^{1.5}\\text {poly}(\\log n))$ time [Daitch-Spielman\, STOC'08]. Our results immediatel y extend to all families of separable graphs. This is joint work with Sall y Dong\, Yu Gao\, Gramoz Goranci\, Yin Tat Lee\, Richard Peng\, and Sushan t Sachdeva.\n LOCATION:https://researchseminars.org/talk/SPAMS/9/ END:VEVENT BEGIN:VEVENT SUMMARY:Nitya Mani (MIT Mathematics) DTSTART:20220224T223000Z DTEND:20220225T000000Z DTSTAMP:20260422T212554Z UID:SPAMS/10 DESCRIPTION:Title: N im and variants\nby Nitya Mani (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\nNim is perhaps the most famous of impart ial combinatorial games\, with a simple solution initially given by Bouton . Many generalizations of Nim and other impartial combinatorial games have been closely studied since the work of Bouton. We will survey a collectio n of interesting Nim variants and some associated results\, along the way encountering Fibonacci numbers\, simple solutions\, and surprisingly compl icated dynamics.\n LOCATION:https://researchseminars.org/talk/SPAMS/10/ END:VEVENT BEGIN:VEVENT SUMMARY:Rachel Zhang (MIT) DTSTART:20220303T230000Z DTEND:20220303T234500Z DTSTAMP:20260422T212554Z UID:SPAMS/11 DESCRIPTION:Title: I nteractive Error Correcting Codes\nby Rachel Zhang (MIT) as part of MI T Simple Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\n\nAbstract\nConsider the task of communicati ng a message x to a receiver in an error resilient way. Classically\, erro r correcting codes provide a non-interactive solution to this problem: the sender can simply encode x using an error correcting code\, so that even if a constant fraction of the bits are adversarially corrupted\, the recei ver can still correctly learn x. In this talk\, I will define the notion o f an interactive error correcting code and show that over a binary alphabe t\, they can tolerate more adversarial erasures than can (non-interactive) error correcting codes. This is joint work with Meghal Gupta and Yael Tau man Kalai.\n LOCATION:https://researchseminars.org/talk/SPAMS/11/ END:VEVENT BEGIN:VEVENT SUMMARY:George Stepaniants (MIT) DTSTART:20220310T223000Z DTEND:20220311T000000Z DTSTAMP:20260422T212554Z UID:SPAMS/12 DESCRIPTION:Title: L earning and predicting complex systems dynamics from single-variable obser vations\nby George Stepaniants (MIT) as part of MIT Simple Person's Ap plied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons B uilding.\n\nAbstract\nAdvances in model inference and data-driven science have enabled the accurate discovery of governing equations from observatio ns alone\, accelerating our understanding and control of dynamical systems . However\, despite the ever-growing amount of experimental data collected \, many physical and biological systems can only be partially observed. He re\, building on recent progress in the inference and integration of nonli near differential equations\, we introduce an approach to learn a model us ing observations of just a single variable within a multi-variable dynamic al system\, and use this model to accurately predict future dynamics. Furt hermore\, we validate our approach on a variety of physical\, chemical and biological systems which exhibit nonlinear dynamics such as relaxation os cillations and limit cycles. This is joint work with Alasdair Hastewell\, Dominic Skinner\, Jan Totz and Jörn Dunkel.\n LOCATION:https://researchseminars.org/talk/SPAMS/12/ END:VEVENT BEGIN:VEVENT SUMMARY:Alex Cohen (MIT Mathematics) DTSTART:20220331T213000Z DTEND:20220331T230000Z DTSTAMP:20260422T212554Z UID:SPAMS/13 DESCRIPTION:Title: A discrete 2D fractal uncertainty principle\nby Alex Cohen (MIT Mathema tics) as part of MIT Simple Person's Applied Mathematics Seminar\n\nLectur e held in Room: 2 - 132 in the Simons Building.\n\nAbstract\nA fractal unc ertainty principle (FUP) states that a function `f' and its Fourier transf orm cannot both be large on a fractal set. These were recently introduced by Semyon Dyatlov and collaborators in order to prove new results in quant um chaos. So far FUPs are only understood for fractal sets in R\, and frac tal sets in $R^2$ remain elusive. In this talk\, we prove a sharp fractal uncertainty principle for Cantor sets in Z/NZ x Z/NZ\, a discrete model fo r $R^2$.\n LOCATION:https://researchseminars.org/talk/SPAMS/13/ END:VEVENT BEGIN:VEVENT SUMMARY:Andrey Khesin (MIT Mathematics) DTSTART:20220407T213000Z DTEND:20220407T230000Z DTSTAMP:20260422T212554Z UID:SPAMS/14 DESCRIPTION:Title: B ound Secrecy and Bound Entanglement: Where (Qu)Bits Go to Die\nby Andr ey Khesin (MIT Mathematics) as part of MIT Simple Person's Applied Mathema tics Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\n\nA bstract\nThere is a surprising result in information theory where the quan tum version of a conjecture is known to be true\, and the classical one re mains open. The conjecture is that there exists a joint probability distri bution for three parties\, Alice\, Bob\, and Eve\, that exhibits bound sec recy. Simply put\, bound secrecy is the idea that there can secret informa tion present in the correlations of the random variables belonging to Alic e and Bob but that is completely unknown to Eve\, and yet despite this\, n o matter what Alice and Bob say to each other publicly\, they will be unab le to distill any bits of a secret key\, random bits completely unknown to Eve. This is a very surprising fact\, as it seems that there is a secret that Alice and Bob share and yet cannot access despite their best efforts. The quantum version of this conjecture states that there exist joint stat es for Alice and Bob which are entangled and therefore cannot be created w ithout spending some amount of entanglement\, but from which no pure entan gled states\, such as Bell pairs\, can be distilled. These joint states ar e called bound entangled\, and not only are they known to exist\, some sma ll examples have been found.\n LOCATION:https://researchseminars.org/talk/SPAMS/14/ END:VEVENT BEGIN:VEVENT SUMMARY:Byron Chin (MIT Mathematics) DTSTART:20220414T213000Z DTEND:20220414T230000Z DTSTAMP:20260422T212554Z UID:SPAMS/15 DESCRIPTION:Title: R econstruction on the stochastic block model\nby Byron Chin (MIT Mathem atics) as part of MIT Simple Person's Applied Mathematics Seminar\n\nLectu re held in Room: 2 - 132 in the Simons Building.\n\nAbstract\nThe problem of community detection is one of great relevance in machine learning and d ata science. The goal is to group vertices that behave similarly within a graph or network. In the context of this problem\, the Stochastic Block Mo del is one of the most well-studied random graph models. In this talk\, we discuss reconstruction results for this model\, highlighting a provably o ptimal algorithm that is closely related to belief propagation.\n LOCATION:https://researchseminars.org/talk/SPAMS/15/ END:VEVENT BEGIN:VEVENT SUMMARY:Brice Huang (MIT Mathematics) DTSTART:20220421T213000Z DTEND:20220421T230000Z DTSTAMP:20260422T212554Z UID:SPAMS/16 DESCRIPTION:Title: T ight Algorithmic Thresholds from the Branching Overlap Gap Property\nb y Brice Huang (MIT Mathematics) as part of MIT Simple Person's Applied Mat hematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\ n\nAbstract\nWe will describe recent progress on algorithmic hardness resu lts for ``spin glass-like" random optimization problems. The landscapes of these problems are highly nonconvex and often include many bad local maxi ma\, impeding optimization by efficient algorithms. As a result\, these pr oblems exhibit gaps between the largest objectives that exist and that can be found by efficient algorithms\; characterizing the algorithmic limit r equires developing sharp hardness results. For mean field spin glasses\, w e describe a new hardness result that tightly characterizes the algorithmi c limit for any algorithm with $O(1)$-Lipschitz dependence on the disorder coefficients. This class includes the best algorithm known for this probl em and natural formulations of gradient descent and approximate message pa ssing. \\\\\n \nWe will go over the Overlap Gap Property (OGP) framework o f Gamarnik and Sudan\, which shows hardness in random optimization problem s against any algorithm that is suitably stable in its inputs. We introduc e the \\emph{Branching OGP}\, a generalization of the OGP to arbitrary ult rametric constellations of solutions\, which is the key tool in the proof of the aforementioned hardness result. By considering the Continuous Rando m Energy Model (CREM)\, we will see by analogy why the Branching OGP yield s tight algorithmic thresholds in mean field spin glasses and potentially in greater generality. \\\\\n \nBased on joint works with Guy Bresler and Mark Sellke.\n LOCATION:https://researchseminars.org/talk/SPAMS/16/ END:VEVENT BEGIN:VEVENT SUMMARY:Anders Aamand (MIT CSAIL) DTSTART:20220428T220000Z DTEND:20220428T230000Z DTSTAMP:20260422T212554Z UID:SPAMS/17 DESCRIPTION:Title: O nline Sorting and its Connection to Geometric Packing Problems\nby And ers Aamand (MIT CSAIL) as part of MIT Simple Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\n\nAbstra ct\nWe investigate various online packing problems in which convex polygon s arrive one by one and have to be placed irrevocably into a container bef ore the next piece is revealed\; the pieces must not be rotated\, but only translated. The aim is to minimize the used space depending on the specif ic problem at hand\, e.g.\, the strip length in strip packing\, the number of bins in bin packing\, etc. \n\n\nWe draw interesting connections to th e following online sorting problem: We receive a stream of real numbers $s _1\, \\cdots \,s_n\,$ each from the unit interval $[0\,1]\,$ one by one. E ach real must be placed in an array with n initially empty cells without k nowing the subsequent arriving reals. The goal is to minimize the sum of d ifferences of consecutive reals in A. The offline optimum is to place the reals in sorted order\, so the cost is at most 1. We will see that no onli ne algorithm can achieve a cost lower than $n^{(1/2)}$ in the worst case. \n\n\nWe use such lower bound to answer several fundamental questions abou t packing. Specifically\, we prove the non-existence of competitive algori thms for various online packing problems. A surprising corollary is that n o online algorithm can pack translates of convex polygons into a unit squa re even if we are guaranteed that the total area of the pieces is at most 0.000001 and the diameter of each piece is at most 0.000001.\n LOCATION:https://researchseminars.org/talk/SPAMS/17/ END:VEVENT BEGIN:VEVENT SUMMARY:Travis Dillon (MIT Mathematics) DTSTART:20220505T220000Z DTEND:20220505T230000Z DTSTAMP:20260422T212554Z UID:SPAMS/18 DESCRIPTION:Title: F air partitioning? It's a piece of cake!\nby Travis Dillon (MIT Mathema tics) as part of MIT Simple Person's Applied Mathematics Seminar\n\nLectur e held in Room: 2 - 132 in the Simons Building.\n\nAbstract\nIs it always possible to cut a cake and distribute the pieces so that everyone at a par ty gets the piece they most desire? We'll show that when it comes to cutti ng cakes\, the old adage that you can't please everybody is dead wrong: Ev eryone can have their cake and eat it\, too. Also\, we'll prove Brouwer's fixed point theorem without using any topology.\n LOCATION:https://researchseminars.org/talk/SPAMS/18/ END:VEVENT BEGIN:VEVENT SUMMARY:Shyam Narayanan (MIT EECS) DTSTART:20221006T213000Z DTEND:20221006T230000Z DTSTAMP:20260422T212554Z UID:SPAMS/19 DESCRIPTION:Title: A n Introduction to Differentially Private Statistics\nby Shyam Narayana n (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\nIn tod ay's era of massive data\, various scientific and technological endeavors have relied on machine learning or statistics models trained on users (e.g .\, medical results from patient data\, better advertisement algorithms fr om phone data\, etc.). Differential Privacy has recently emerged as one of the most popular methods to protect the privacy of users. In this talk\, I will be giving an overview of differential privacy and will focus on how we can solve various statistical problems\, such as estimating the mean a nd covariance of Multivariate Gaussian distributions\, with differential p rivacy using few samples. If time permits\, I will describe some more rece nt advanced methods of solving these problems with even fewer samples.\n LOCATION:https://researchseminars.org/talk/SPAMS/19/ END:VEVENT BEGIN:VEVENT SUMMARY:Brice Huang (MIT EECS) DTSTART:20221013T220000Z DTEND:20221013T224500Z DTSTAMP:20260422T212554Z UID:SPAMS/20 DESCRIPTION:Title: A n Introduction to Random Optimization Problems\nby Brice Huang (MIT EE CS) as part of MIT Simple Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\n\nAbstract\nOptimization li es at the heart of many computation tasks\, such as training a neural netw ork. These optimization problems arise from stochastic data and are often high-dimensional and non-convex. In this talk\, I will overview recently d eveloped algorithms for one random optimization problem\, the mixed p-spin glass\, and how they generalize to other problems. If time permits I will discuss recent lower bounds suggesting that these algorithms are optimal. \n LOCATION:https://researchseminars.org/talk/SPAMS/20/ END:VEVENT BEGIN:VEVENT SUMMARY:Lichen Zhang (MIT Mathematics) DTSTART:20221027T220000Z DTEND:20221027T224500Z DTSTAMP:20260422T212554Z UID:SPAMS/21 DESCRIPTION:Title: S ketching as a tool for fast optimization\nby Lichen Zhang (MIT Mathema tics) as part of MIT Simple Person's Applied Mathematics Seminar\n\nLectur e held in Room: 2 - 132 in the Simons Building.\n\nAbstract\n\\noindent Sk etching is a powerful tool with many applications including regression\, l ow-rank approximation\, and preconditioning. Given an n-by-d matrix A with n much larger than d\, sketching describes a distribution on random matri ces such that an element S of this distribution is an s-by-n matrix such t hat for any d-dimensional $ vector x\, || SAx ||_2^2 <= (1+eps) || Ax ||_2 ^2$ \, and $ s = poly(d\, 1/eps\, 1/delta) $ is independent of n.\n\n\\vsp ace{1ex}\n\n\\noindent In this talk\, I survey another direction that uses sketching to speed up optimization algorithms. I’ll show how to design a good distribution of sketching matrices so that they can be used for \\\ \\n1). Compressed gradient descent\, \n2). Linear programming and empirica l risk minimization. \\\\\n\n\\vspace{1ex}\n\n\\noindent We will see how s ketching enables us to develop novel data structures for numerical linear algebra problems\, which are the backbones of recent breakthroughs in fast optimization algorithms. If time permits\, I’ll also touch on using dif ferential privacy (in a very surprising way) to improve the performance of the sketching data structure. \\\\\n LOCATION:https://researchseminars.org/talk/SPAMS/21/ END:VEVENT END:VCALENDAR