BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CMSA - ECPv6.16.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:CMSA
X-ORIGINAL-URL:https://cmsa.fas.harvard.edu
X-WR-CALDESC:Events for CMSA
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20160313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20161106T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20170312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20171105T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20180311T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20181104T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20170215T150000
DTEND;TZID=America/New_York:20171214T160000
DTSTAMP:20260730T185831
CREATED:20240124T064532Z
LAST-MODIFIED:20240124T065049Z
UID:10001332-1487170800-1513267200@cmsa.fas.harvard.edu
SUMMARY:Random Matrix & Probability Theory Seminar (2016-2017)
DESCRIPTION:The random matrix and probability theory will be every Wednesday from 3pm-4pm in CMSA Building\, 20 Garden Street\, Room G10.
URL:https://cmsa.fas.harvard.edu/event/random-matrix-probability-theory-seminar-2016-2017/
LOCATION:CMSA Room G10\, CMSA\, 20 Garden Street\, Cambridge\, MA\, 02138\, United States
CATEGORIES:Random Matrix & Probability Theory Seminar
ATTACH;FMTTYPE=image/jpeg:https://cmsa.fas.harvard.edu/media/DSC_0025-768x512-1.jpg
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20171002T090000
DTEND;TZID=America/New_York:20171006T160000
DTSTAMP:20260730T185831
CREATED:20230717T173144Z
LAST-MODIFIED:20250304T211134Z
UID:10000037-1506934800-1507305600@cmsa.fas.harvard.edu
SUMMARY:Workshop on Additive Combinatorics\, Oct. 2-6\, 2017
DESCRIPTION:The workshop on additive combinatorics will take place October 2-6\, 2017 at the Center of Mathematical Sciences and Applications\, located at 20 Garden Street\, Cambridge\, MA. \nAdditive combinatorics is a mathematical area bordering on number theory\, discrete mathematics\, harmonic analysis and ergodic theory. It has achieved a number of successes in pure mathematics in the last two decades in quite diverse directions\, such as: \n\nThe first sensible bounds for Szemerédi’s theorem on progressions (Gowers);\nLinear patterns in the primes (Green\, Tao\, Ziegler);\nConstruction of expanding sets in groups and expander graphs (Bourgain\, Gamburd);\nThe Kakeya Problem in Euclidean harmonic analysis (Bourgain\, Katz\, Tao).\n\nIdeas and techniques from additive combinatorics have also had an impact in theoretical computer science\, for example \n\nConstructions of pseudorandom objects (eg. extractors and expanders);\nConstructions of extremal objects (eg. BCH codes);\nProperty testing (eg. testing linearity);\nAlgebraic algorithms (eg. matrix multiplication).\n\nThe main focus of this workshop will be to bring together researchers involved in additive combinatorics\, with a particular inclination towards the links with theoretical computer science. Thus it is expected that a major focus will be additive combinatorics on the boolean cube (Z/2Z)^n \, which is the object where the exchange of ideas between pure additive combinatorics and theoretical computer science is most fruitful. Another major focus will be the study of pseudorandom phenomena in additive combinatorics\, which has been an important contributor to modern methods of generating provably good randomness through deterministic methods. Other likely topics of discussion include the status of major open problems (the polynomial Freiman-Ruzsa conjecture\, inverse theorems for the Gowers norms with bounds\, explicit correlation bounds against low degree polynomials) as well as the impact of new methods such as the introduction of algebraic techniques by Croot–Pach–Lev and Ellenberg–Gijswijt. \nConfirmed participants include: \n\nArnab Bhattacharyya (Indian Institute of Science)\nThomas Bloom (University of Bristol)\nJop Briët (Centrum Wiskunde & Informatica\, Amsterdam)\nMei-Chu Chang (University of California\, Riverside)\nNoam Elkies (Harvard University)\nAsaf Ferber (MIT)\nJacob Fox (Stanford University)\nShafi Goldwasser (MIT)\nElena Grigorescu (Purdue University)\nHamed Hatami (McGill University)\nPooya Hatami (Institute for Advanced Study)\nKaave Hosseini (University of California\, San Diego)\nGuy Kindler (Hebrew University of Jerusalem)\nVsevolod Lev (University of Haifa at Oranim)\nSean Prendiville (University of Manchester)\nRonitt Rubinfeld (MIT)\nWill Sawin (ETH Zürich)\nFernando Shao (Oxford University)\nOlof Sisask (KTH Royal Institute of Technology)\nMadhur Tulsiani (University of Chicago)\nJulia Wolf (University of Bristol)\nEmanuele Viola (Northeastern University)\nYufei Zhao (MIT)\n\nCo-organizers of this workshop include Ben Green\, Swastik Kopparty\, Ryan O’Donnell\, Tamar Ziegler. \nMonday\, October 2 \n\n\n\nTime\nSpeaker\nTitle/Abstract\n\n\n9:00-9:30am\nBreakfast\n \n\n\n9:30-10:20am\nJacob Fox\nTower-type bounds for Roth’s theorem with popular differences \nAbstract: A famous theorem of Roth states that for any $\alpha > 0$ and $n$ sufficiently large in terms of $\alpha$\, any subset of $\{1\, \dots\, n\}$ with density $\alpha$ contains a 3-term arithmetic progression. Green developed an arithmetic regularity lemma and used it to prove that not only is there one arithmetic progression\, but in fact there is some integer $d > 0$ for which the density of 3-term arithmetic progressions with common difference $d$ is at least roughly what is expected in a random set with density $\alpha$. That is\, for every $\epsilon > 0$\, there is some $n(\epsilon)$ such that for all $n > n(\epsilon)$ and any subset $A$ of $\{1\, \dots\, n\}$ with density $\alpha$\, there is some integer $d > 0$ for which the number of 3-term arithmetic progressions in $A$ with common difference $d$ is at least $(\alpha^3-\epsilon)n$. We prove that $n(\epsilon)$ grows as an exponential tower of 2’s of height on the order of $\log(1/\epsilon)$. We show that the same is true in any abelian group of odd order $n$. These results are the first applications of regularity lemmas for which the tower-type bounds are shown to be necessary. \nThe first part of the talk by Jacob Fox includes an overview and discusses the upper bound. The second part of the talk by Yufei Zhao focuses on the lower bound construction and proof. These results are all joint work with Huy Tuan Pham.\n\n\n10:20-11:00am\nCoffee Break\n \n\n\n11:00-11:50am\nYufei Zhao\nTower-type bounds for Roth’s theorem with popular differences \nAbstract:  Continuation of first talk by Jacob Fox. The first part of the talk by Jacob Fox includes an overview and discusses the upper bound. The second part of the talk by Yufei Zhao focuses on the lower bound construction and proof. These results are all joint work with Huy Tuan Pham.\n\n\n12:00-1:30pm\nLunch\n \n\n\n1:30-2:20pm\nJop Briët\nLocally decodable codes and arithmetic progressions in random settings \nAbstract: This talk is about a common feature of special types of error correcting codes\, so-called locally decodable codes (LDCs)\, and two problems on arithmetic progressions in random settings\, random differences in Szemerédi’s theorem and upper tails for arithmetic progressions in a random set in particular. It turns out that all three can be studied in terms of the Gaussian width of a set of vectors given by a collection of certain polynomials. Using a matrix version of the Khintchine inequality and a lemma that turns such polynomials into matrices\, we give an alternative proof for the best-known lower bounds on LDCs and improved versions of prior results due to Frantzikinakis et al. and Bhattacharya et al. on arithmetic progressions in the aforementioned random settings. \nJoint work with Sivakanth Gopi\n\n\n2:20-3:00pm\nCoffee Break\n \n\n\n3:00-3:50pm\nFernando Shao\n\nLarge deviations for arithmetic progressions \nAbstract: We determine the asymptotics of the log-probability that the number of k-term arithmetic progressions in a random subset of integers exceeds its expectation by a constant factor. This is the arithmetic analog of subgraph counts in a random graph. I will highlight some open problems in additive combinatorics that we encountered in our work\, namely concerning the “complexity” of the dual functions of AP-counts. \n\n\n\n4:00-6:00pm\nWelcome Reception\n\n\n\n\nTuesday\, October 3 \n\n\n\nTime\nSpeaker\nTitle/Abstract\n\n\n9:00-9:30am\nBreakfast\n\n\n\n9:30-10:20am\nEmanuele Viola\nInterleaved group products \nAuthors: Timothy Gowers and Emanuele Viola \nAbstract: Let G be the special linear group SL(2\,q). We show that if (a1\,a2) and (b1\,b2) are sampled uniformly from large subsets A and B of G^2 then their interleaved product a1 b1 a2 b2 is nearly uniform over G. This extends a result of Gowers (2008) which corresponds to the independent case where A and B are product sets. We obtain a number of other results. For example\, we show that if X is a probability distribution on G^m such that any two coordinates are uniform in G^2\, then a pointwise product of s independent copies of X is nearly uniform in G^m\, where s depends on m only. Similar statements can be made for other groups as well. \nThese results have applications in computer science\, which is the area where they were first sought by Miles and Viola (2013).\n\n\n10:20-11:00am\nCoffee Break\n\n\n\n11:00-11:50am\nVsevolod Lev\nOn Isoperimetric Stability \nAbstract: We show that a non-empty subset of an abelian group with a small edge boundary must be large; in particular\, if $A$ and $S$ are finite\, non-empty subsets of an abelian group such that $S$ is independent\, and the edge boundary of $A$ with respect to $S$ does not exceed $(1-c)|S||A|$ with a real $c\in(0\,1]$\, then $|A|\ge4^{(1-1/d)c|S|}$\, where $d$ is the smallest order of an element of $S$. Here the constant $4$ is best possible. \nAs a corollary\, we derive an upper bound for the size of the largest independent subset of the set of popular differences of a finite subset of an abelian group. For groups of exponent $2$ and $3$\, our bound translates into a sharp estimate for the additive  dimension of the popular difference set. \nWe also prove\, as an auxiliary result\, the following estimate of possible independent interest: if $A\subseteq{\mathbb Z}^n$ is a finite\, non-empty downset\, then\, denoting by $w(z)$ the number of non-zero components of the vector $z\in\mathbb{Z}^n$\, we have   $$ \frac1{|A|} \sum_{a\in A} w(a) \le \frac12\\, \log_2 |A|. $$\n\n\n12:00-1:30pm\nLunch\n\n\n\n1:30-2:20pm\nElena Grigorescu\nNP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem \nAbstract: I will discuss the complexity of decoding Reed-Solomon codes\, and some results establishing NP-hardness for asymptotically smaller decoding radii than the maximum likelihood decoding radius. These results follow from the study of a generalization of the classical Subset Sum problem to higher moments\, which may be of independent interest. I will further discuss a connection with the Prouhet-Tarry-Escott problem studied in Number Theory\, which turns out to capture a main barrier in extending our techniques to smaller radii. \nJoint work with Venkata Gandikota and Badih Ghazi.\n\n\n2:20-3:00pm\nCoffee Break\n\n\n\n3:00-3:50pm\nSean Prendiville\nPartition regularity of certain non-linear Diophantine equations. \nAbstract:  We survey some results in additive Ramsey theory which remain valid when variables are restricted to sparse sets of arithmetic interest\, in particular the partition regularity of a class of non-linear Diophantine equations in many variables.\n\n\n\nWednesday\, October 4 \n\n\n\nTime\nSpeaker\nTitle/Abstract\n\n\n9:00-9:30am\nBreakfast\n \n\n\n9:30-10:20am\nOlof Sisask\nBounds on capsets via properties of spectra \nAbstract: A capset in F_3^n is a subset A containing no three distinct elements x\, y\, z satisfying x+z=2y. Determining how large capsets can be has been a longstanding problem in additive combinatorics\, particularly motivated by the corresponding question for subsets of {1\,2\,…\,N}. While the problem in the former setting has seen spectacular progress recently through the polynomial method of Croot–Lev–Pach and Ellenberg–Gijswijt\, such progress has not been forthcoming in the setting of the integers. Motivated by an attempt to make progress in this setting\, we shall revisit the approach to bounding the sizes of capsets using Fourier analysis\, and in particular the properties of large spectra. This will be a two part talk\, in which many of the ideas will be outlined in the first talk\, modulo the proof of a structural result for sets with large additive energy. This structural result will be discussed in the second talk\, by Thomas Bloom\, together with ideas on how one might hope to achieve Behrend-style bounds using this method. \nJoint work with Thomas Bloom.\n\n\n10:20-11:00am\nCoffee Break\n \n\n\n11:00-11:50am\nThomas Bloom\nBounds on capsets via properties of spectra \nThis is a continuation of the previous talk by Olof Sisask.\n\n\n12:00-1:30pm\nLunch\n \n\n\n1:30-2:20pm\nHamed Hatami\nPolynomial method and graph bootstrap percolation \nAbstract: We introduce a simple method for proving lower bounds for the size of the smallest percolating set in a certain graph bootstrap process. We apply this method to determine the sizes of the smallest percolating sets in multidimensional tori and multidimensional grids (in particular hypercubes). The former answers a question of Morrison and Noel\, and the latter provides an alternative and simpler proof for one of their main results. This is based on a joint work with Lianna Hambardzumyan and Yingjie Qian.\n\n\n2:20-3:00pm\nCoffee Break\n\n\n\n3:00-3:50pm\nArnab Bhattacharyya\nAlgorithmic Polynomial Decomposition \nAbstract: Fix a prime p. Given a positive integer k\, a vector of positive integers D = (D_1\, …\, D_k) and a function G: F_p^k → F_p\, we say a function P: F_p^n → F_p admits a (k\, D\, G)-decomposition if there exist polynomials P_1\, …\, P_k: F_p^n -> F_p with each deg(P_i) <= D_i such that for all x in F_p^n\, P(x) = G(P_1(x)\, …\, P_k(x)). For instance\, an n-variate polynomial of total degree d factors nontrivially exactly when it has a (2\, (d-1\, d-1)\, prod)-decomposition where prod(a\,b) = ab. \nWhen show that for any fixed k\, D\, G\, and fixed bound d\, we can decide whether a given polynomial P(x_1\, …\, x_n) of degree d admits a (k\,D\,G)-decomposition and if so\, find a witnessing decomposition\, in poly(n) time. Our approach is based on higher-order Fourier analysis. We will also discuss improved analyses and algorithms for special classes of decompositions. \nJoint work with Pooya Hatami\, Chetan Gupta and Madhur Tulsiani.\n\n\n\nThursday\, October 5 \n\n\n\nTime\nSpeaker\nTitle/Abstract\n\n\n9:00-9:30am\nBreakfast\n\n\n\n9:30-10:20am\nMadhur Tulsiani\nHigher-order Fourier analysis and approximate decoding of Reed-Muller codes \n Abstract: Decomposition theorems proved by Gowers and Wolf provide an appropriate notion of “Fourier transform” for higher-order Fourier analysis. I will discuss some questions and techniques that arise from trying to develop polynomial time algorithms for computing these decompositions. \nI will discuss constructive proofs of these decompositions based on boosting\, which reduce the problem of computing these decompositions to a certain kind of approximate decoding problem for codes. I will also discuss some earlier and recent works on this decoding problem. \nBased on joint works with Arnab Bhattacharyya\, Eli Ben-Sasson\, Pooya Hatami\, Noga Ron-Zewi and Julia Wolf.\n\n\n10:20-11:00am\nCoffee Break\n\n\n\n11:00-11:50am\nJulia Wolf\nStable arithmetic regularity \nThe arithmetic regularity lemma in the finite-field model\, proved by Green in 2005\, states that given a subset A of a finite-dimensional vector space over a prime field\, there exists a subspace H of bounded codimension such that A is Fourier-uniform with respect to almost all cosets of H. It is known that in general\, the growth of the codimension of H is required to be of tower type depending on the degree of uniformity\, and that one must allow for a small number of non-uniform cosets. \nOur main result is that\, under a natural model-theoretic assumption of stability\, the tower-type bound and non-uniform cosets in the arithmetic regularity lemma are not necessary.  Specifically\, we prove an arithmetic regularity lemma for k-stable subsets in which the bound on the codimension of the subspace is a polynomial (depending on k) in the degree of uniformity\, and in which there are no non-uniform cosets. \nThis is joint work with Caroline Terry. \n\n\n\n12:00-1:30pm\nLunch\n \n\n\n1:30-2:20pm\nWill Sawin\n\nConstructions of Additive Matchings \nAbstract: I will explain my work\, with Robert Kleinberg and David Speyer\, constructing large tri-colored sum-free sets in vector spaces over finite fields\, and how it shows that some additive combinatorics problems over finite fields are harder than corresponding problems over the integers.  \n\n\n\n2:20-3:00pm\nCoffee Break\n\n\n\n3:00-3:50pm\nMei-Chu Chang\nArithmetic progressions in multiplicative groups of finite fields \nAbstract:   Let G be a multiplicative subgroup of the prime field F_p of size |G|> p^{1-\kappa} and r an arbitrarily fixed positive integer. Assuming \kappa=\kappa(r)>0 and p large enough\, it is shown that any proportional subset A of G contains non-trivial arithmetic progressions of length r.\n\n\n\nFriday\, October 6 \n\n\n\nTime\nSpeaker\nTitle/Abstract\n\n\n9:00-9:30am\nBreakfast\n\n\n\n9:30-10:20am\nAsaf Ferber\nOn a resilience version of the Littlewood-Offord problem \nAbstract:  In this talk we consider a resilience version of the classical Littlewood-Offord problem. That is\, consider the sum X=a_1x_1+…a_nx_n\, where the a_i-s are non-zero reals and x_i-s are i.i.d. random variables with     (x_1=1)= P(x_1=-1)=1/2. Motivated by some problems from random matrices\, we consider the question: how many of the x_i-s  can we typically allow an adversary to change without making X=0? We solve this problem up to a constant factor and present a few interesting open problems. \nJoint with: Afonso Bandeira (NYU) and Matthew Kwan (ETH\, Zurich).\n\n\n10:20-11:00am\nCoffee Break\n\n\n\n11:00-11:50am\nKaave Hosseini\nProtocols for XOR functions and Entropy decrement \nAbstract: Let f:F_2^n –> {0\,1} be a function and suppose the matrix M defined by M(x\,y) = f(x+y) is partitioned into k monochromatic rectangles.  We show that F_2^n can be partitioned into affine subspaces of co-dimension polylog(k) such that f is constant on each subspace. In other words\, up to polynomial factors\, deterministic communication complexity and parity decision tree complexity are equivalent. \nThis relies on a novel technique of entropy decrement combined with Sanders’ Bogolyubov-Ruzsa lemma. \nJoint work with Hamed Hatami and Shachar Lovett\n\n\n12:00-1:30pm\nLunch\n\n\n\n1:30-2:20pm\nGuy Kindler\n\nFrom the Grassmann graph to Two-to-Two games \nAbstract: In this work we show a relation between the structure of the so called Grassmann graph over Z_2 and the Two-to-Two conjecture in computational complexity. Specifically\, we present a structural conjecture concerning the Grassmann graph (together with an observation by Barak et. al.\, one can view this as a conjecture about the structure of non-expanding sets in that graph) which turns out to imply the Two-to-Two conjecture. \nThe latter conjecture its the lesser-known and weaker sibling of the Unique-Games conjecture [Khot02]\, which states that unique games (a.k.a. one-to-one games) are hard to approximate. Indeed\, if the Grassmann-Graph conjecture its true\, it would also rule out some attempts to refute the Unique-Games conjecture\, as these attempts provide potentially efficient algorithms to solve unique games\, that would actually also solve two-to-two games if they work at all. \nThese new connections between the structural properties of the Grassmann graph and complexity theoretic conjectures highlight the Grassmann graph as an interesting and worthy object of study. We may indicate some initial results towards analyzing its structure. \nThis is joint work with Irit Dinur\, Subhash Khot\, Dror Minzer\, and Muli Safra. \n\n\n\n\n\n\n\nEvents\,Past Events
URL:https://cmsa.fas.harvard.edu/event/workshop-on-additive-combinatorics-oct-2-6-2017/
LOCATION:CMSA\, 20 Garden Street\, Cambridge\, MA\, 02138\, United States
CATEGORIES:Event,Workshop
END:VEVENT
END:VCALENDAR