Growth and zero sets of eigenfunctions and of solutions to elliptic partial differential equations
2019-02-25 09:30 - 2019-03-01 17:00 (America/New_York) | CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
From February 25 to March 1, the CMSA will be hosting a workshop on Growth and zero sets of eigenfunctions and of solutions to elliptic partial differential equations.
Key participants of this workshop include David Jerison (MIT), Alexander Logunov (IAS), and Eugenia Malinnikova (IAS). This workshop will have morning sessions on Monday-Friday of this week from 9:30-11:30am, and afternoon sessions on Monday, Tuesday, and Thursday from 3:00-5:00pm.
The sessions will be held in (G02) (downstairs) at 20 Garden, except for Tuesday afternoon, when the talk will be in (G10).

Optimally Imprecise Memory and Biased Forecasts
2019-02-20 16:30 - 17:30
Speaker: Michael Woodford (Columbia)
Title: Optimally Imprecise Memory and Biased Forecasts
Abstract: We propose a model of optimal decision making subject to a memory constraint. The constraint is a limit on the complexity of memory measured using Shannon’s mutual information, as in models of rational inattention; the structure of the imprecise memory is optimized (for a given decision problem and noisy environment) subject to this constraint. We characterize the form of the optimally imprecise memory, and show that the model implies that both forecasts and actions will exhibit idiosyncratic random variation; that beliefs will fluctuate forever around the rational-expectations (perfect-memory) beliefs with a variance that does not fall to zero; and that more recent news will be given disproportionate weight. The model provides a simple explanation for a number of features of observed forecast bias in laboratory and field settings. [Joint work with Rava Azeredo da Silveira and Yeji Sung

Inference for the Mean
2019-02-07 16:30 - 17:30
Speaker: Ulrich Mueller (Princeton)
Title: Inference for the Mean
Abstract: Consider inference about the mean of a population with finite variance, based on an i.i.d. sample. The usual t-statistic yields correct inference in large samples, but heavy tails induce poor small sample behavior. This paper combines extreme value theory for the smallest and largest observations with a normal approximation for the t-statistic of a truncated sample to obtain more accurate inference. This alternative approximation is shown to provide a refinement over the standard normal approximation to the full sample t-statistic under more than two but less than three moments, while the bootstrap does not. Small sample simulations suggest substantial size improvements over the bootstrap.

Innovation in Cell Phones in the US and China: Who Improves Technology Faster?
2019-01-19 16:30
Speaker: Richard B. Freeman (Harvard University and NBER)
Title: Innovation in Cell Phones in the US and China: Who Improves Technology Faster?
Abstract: Cell phones are the archetypical modern consumer innovation, spreading around the world at an incredible pace, extensively used for connecting people with the Internet and diverse apps. Consumers report spending from 2-5 hours a day at their cell phones, with 44% of Americans saying “couldn’t go a day without their mobile devices.” Cell phone manufacturers introduce new models regularly, embodying additional features while other firms produce new applications that increase demand for the phones. Using newly developed data on the prices, attributes, and sales of different models in the US and China, this paper estimates the magnitude of technological change in the phones in the 2000s. It explores the problems of analyzing a product with many interactive attributes in the standard hedonic price regression model and uses Principal Components Regression to reduce dimensionality. The main finding is that technology improved the value of cell phones at comparable rates in the US and China, despite different market structures and different evaluations of some attributes and brands. The study concludes with a discussion of ways to evaluate the economic surplus created by the cell phones and their contribution to economic well-being.

Geometric Analysis Approach to AI Workshop
2019-01-18 08:30 - 2019-01-21 17:30
Due to inclement weather on Sunday, the second half of the workshop has been moved forward one day. Sunday and Monday’s talks will now take place on Monday and Tuesday.
On January 18-21, 2019 the Center of Mathematical Sciences and Applications will be hosting a workshop on the Geometric Analysis Approach to AI.
This workshop will focus on the theoretic foundations of AI, especially various methods in Deep Learning. The topics will cover the relationship between deep learning and optimal transportation theory, DL and information geometry, DL Learning and information bottle neck and renormalization theory, DL and manifold embedding and so on. Furthermore, the recent advancements, novel methods, and real world applications of Deep Learning will also be reported and discussed.
The workshop will take place from January 18th to January 23rd, 2019. In the first four days, from January 18th to January 21, the speakers will give short courses; On the 22nd and 23rd, the speakers will give conference representations. This workshop is organized by Xianfeng Gu and Shing-Tung Yau.
The workshop will be held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA.
Speakers:

Sarah Adel Bargal, Boston University
Guy Bresler, MIT
Tina Eliassi-Rad, Northeastern
Yun Raymond Fu, Northeastern
Brian Kulis, Boston University
Na Lei, Dalian University of Technology
Yi Ma, UC Berkeley
Minh Hoai Nguyen, Stony Brook
Francesco Orabona, Boston University
Cengiz Pehlevan, Harvard SEAS
Tomaso Poggio, MIT
Zhiwei Qin, DiDi Research America
Kate Saenko, Boston University
Dimitris Samaras, Stony Brook
Johannes Schmidt-Hieber, University of Twente
Steven Skiena, Stony Brook
Vivienne Sze, MIT
Naftali Tishby, ICNC
Jiajun Wu, MIT
Ying Nian Wu, UCLA
Gangqiang Xia, Morgan Stanley
Eric Xing, Carnegie Mellon
Donghui Yan, UMass Dartmouth
Alan Yuille, Johns Hopkins
Juhua Zhu, Argus

Displacement convexity of Boltzmann's entropy characterizes positive energy in general relativity
2018-12-05 16:30 - 17:30
Speaker: Robert McCann (University of Toronto)
Title: Displacement convexity of Boltzmann’s entropy characterizes positive energy in general relativity
Abstract: Einstein’s theory of gravity is based on assuming that the fluxes of a energy and momentum in a physical system are proportional to a certain variant of the Ricci curvature tensor on a smooth 3+1 dimensional spacetime. The fact that gravity is attractive rather than repulsive is encoded in the positivity properties which this tensor is assumed to satisfy. Hawking and Penrose (1971) used this positivity of energy to give conditions under which smooth spacetimes must develop singularities. By lifting fractional powers of the Lorentz distance between points on a globally hyperbolic spacetime to probability measures on spacetime events, we show that the strong energy condition of Hawking and Penrose is equivalent to convexity of the Boltzmann-Shannon entropy along the resulting geodesics of probability measures. This new characterization of the strong energy condition on globally hyperbolic manifolds also makes sense in (non-smooth) metric measure settings, where it has the potential to provide a framework for developing a theory of gravity which admits certain singularities and can be continued beyond them. It provides a Lorentzian analog of Lott, Villani and Sturm’s metric-measure theory of lower Ricci bounds, and hints at new connections linking gravity to the second law of thermodynamics. Preprint available at http://www.math.toronto.edu/mccann/papers/GRO.pdf

Morphogenesis: Geometry and Physics
2018-12-03 08:30 - 2018-12-05 14:30
Just over a century ago, the biologist, mathematician and philologist D’Arcy Thompson wrote “On growth and form”. The book – a literary masterpiece – is a visionary synthesis of the geometric biology of form. It also served as a call for mathematical and physical approaches to understanding the evolution and development of shape. In the century since its publication, we have seen a revolution in biology following the discovery of the genetic code, which has uncovered the molecular and cellular basis for life, combined with the ability to probe the chemical, structural, and dynamical nature of molecules, cells, tissues and organs across scales. In parallel, we have seen a blossoming of our understanding of spatiotemporal patterning in physical systems, and a gradual unveiling of the complexity of physical form. So, how far are we from realizing the century-old vision that “Cell and tissue, shell and bone, leaf and flower, are so many portions of matter, and it is in obedience to the laws of physics that their particles have been moved, moulded and conformed ?”
To address this requires an appreciation of the enormous ‘morphospace’ in terms of the potential shapes and sizes that living forms take, using the language of mathematics. In parallel, we need to consider the biological processes that determine form in mathematical terms is based on understanding how instabilities and patterns in physical systems might be harnessed by evolution.
In Fall 2018, CMSA will focus on a program that aims at recent mathematical advances in describing shape using geometry and statistics in a biological context, while also considering a range of physical theories that can predict biological shape at scales ranging from macromolecular assemblies to whole organ systems.
The first workshop will focus on the interface between Morphometrics and Mathematics, while the second will focus on the interface between Morphogenesis and Physics.The workshop is organized by L. Mahadevan (Harvard), O. Pourquie (Harvard), A. Srivastava (Florida).
As part of the program on Mathematical Biology a workshop on Morphogenesis: Geometry and Physics will take place on December 3-5, 2018. The workshop will be held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA.
Videos
Speakers:

Arkhat Abzhanov, Imperial College
Yohanns Bellaiche, Paris
Cheng Ming Chuong, USC
Zev Gartner, UCSF
Thomas Gregor, Princeton
Dagmar Iber, Zurich
Ian Jermyn, Durham University
Raymond Keller, UVA
Allon Klein, HMS
Lisa Manning, Syracuse
Cristina Marchetti, UCSB
Sean Megason, HMS
Elliot Meyerowitz, Caltech
Michel Milinkovitch, Geneva
Leonardo Morsut, USC
Olivier Pourquié, HMS
Eric Siggia, Rockefeller University
Ben Simons, Cambridge
Sebastian Streichan, UCSB
Aryeh Warmflash, Rice

Recent progress on mean curvature flow
2018-11-28 16:30 - 17:30
Speaker: Robert Haslhofer (University of Toronto)
Title: Recent progress on mean curvature flow
Abstract: A family of surfaces moves by mean curvature flow if the velocity at each point is given by the mean curvature vector. Mean curvature flow is the most natural evolution in extrinsic geometry and shares many features with Hamilton’s Ricci flow from intrinsic geometry. In the first half of the talk, I will give an overview of the well developed theory in the mean convex case, i.e. when the mean curvature vector everywhere on the surface points inwards. Mean convex mean curvature flow can be continued through all singularities either via surgery or as level set solution, with a precise structure theory for the singular set. In the second half of the talk, I will report on recent progress in the general case without any curvature assumptions. Namely, I will describe our solution of the mean convex neighborhood conjecture and the nonfattening conjecture, as well as a general classification result for all possible blowup limits near spherical or cylindrical singularities. In particular, assuming Ilmanen’s multiplicity one conjecture, we conclude that for embedded two-spheres the mean curvature flow through singularities is well-posed. This is joint work with Kyeongsu Choi and Or Hershkovits.

Computational Principles of Auditory Cortex
2018-11-19 15:00 - 16:00
Speaker: Xiaoqin Wang (Johns Hopkins University)
Title: Computational Principles of Auditory Cortex
Abstract: Auditory cortex is located at the top of a hierarchical processing pathway in the brain that encodes acoustic information. This brain region is crucial for speech and music perception and vocal production. Auditory cortex has long been considered a difficult brain region to study and remained one of less understood sensory cortices. Studies have shown that neural computation in auditory cortex is highly nonlinear. In contrast to other sensory systems, the auditory system has a longer pathway between sensory receptors and the cerebral cortex. This unique organization reflects the needs of the auditory system to process time-varying and spectrally overlapping acoustic signals entering the ears from all spatial directions at any given time. Unlike visual or somatosensory cortices, auditory cortex must also process and differentiate sounds that are externally generated or self-produced (during speaking). Neural representations of acoustic information in auditory cortex are shaped by auditory feedback and vocal control signals during speaking. Our laboratory has developed a unique and highly vocal non-human primate model (the common marmoset) and quantitative tools to study neural mechanisms underlying audition and vocal communication.

The virtual fundamental class in symplectic geometry
2018-11-14 16:00 - 17:00
Speaker: Dusa McDuff (Columbia University)
Title: The virtual fundamental class in symplectic geometry
Abstract: Essential to many constructions and applications of symplectic geometry is the ability to count J-holomorphic curves. The moduli spaces of such curves have well understood compactifications, and if cut out transversally are oriented manifolds of dimension equal to the index of the problem, so that they a fundamental class that can be used to count curves. In the general case, when the defining equation is not transverse, there are various different approaches to constructing a representative for this class, We will discuss and compare different approaches to such a construction e.g. using polyfolds or various kinds of finite dimensional reduction. Most of this is joint work with Katrin Wehrheim.

Exploring the (massive) space of graph partitions
2018-10-31 16:30 - 17:30
Speaker: Moon Duchin (Tufts)
Title: Exploring the (massive) space of graph partitions
Abstract: The problem of electoral redistricting can be set up as a search of the space of partitions of a graph (representing the units of a state or other jurisdiction) subject to constraints (state and federal rules about the properties of districts). I’ll survey the problem and some approaches to studying it, with an emphasis on the deep mathematical questions it raises, from combinatorial enumeration to discrete differential geometry to dynamics.

Mathematical Biology
2018-10-22 09:00 - 2019-04-17 17:00
During Academic year 2018-19, the CMSA will be hosting a Program on Mathematical Biology.
Just over a century ago, the biologist, mathematician and philologist D’Arcy Thompson wrote “On growth and form”. The book was a visionary synthesis of the geometric biology of form at the time. It also served as a call for mathematical and physical approaches to understanding the evolution and development of shape.
In the century since its publication, we have seen a revolution in biology following the discovery of the genetic code, which has uncovered the molecular and cellular basis for life, combined with the ability to probe the chemical, structural, and dynamical nature of molecules, cells, tissues and organs across scales. In parallel, we have seen a blossoming of our understanding of spatiotemporal patterning in physical systems, and a gradual unveiling of the complexity of physical form. And in mathematics and computation, there has been a revolution in terms of posing and solving problems at the intersection of computational geometry, statistics and inference. So, how far are we from realizing a descriptive, predictive and controllable theory of biological shape?
In Fall 2018, CMSA will focus on a program that aims at recent mathematical advances in describing shape using geometry and statistics in a biological context, while also considering a range of physical theories that can predict biological shape at scales ranging from macromolecular assemblies to whole organ systems
The CMSA will be hosting three workshops as part of this program. The Workshop on Morphometrics, Morphogenesis and Mathematics will take place on October 22-26.
A workshop on Morphogenesis: Geometry and Physics will take place on December 3-6, 2018.
A workshop on Invariance and Geometry in Sensation, Action and Cognition will take place on April 15-17, 2019.

Workshop on Morphometrics, Morphogenesis and Mathematics
2018-10-22 08:30 - 2018-10-24 14:00
In Fall 2018, the CMSA will host a Program on Mathematical Biology, which aims to describe recent mathematical advances in using geometry and statistics in a biological context, while also considering a range of physical theories that can predict biological shape at scales ranging from macromolecular assemblies to whole organ systems.
The plethora of natural shapes that surround us at every scale is both bewildering and astounding – from the electron micrograph of a polyhedral virus, to the branching pattern of a gnarled tree to the convolutions in the brain. Even at the human scale, the shapes seen in a garden at the scale of a pollen grain, a seed, a sapling, a root, a flower or leaf are so numerous that “it is enough to drive the sanest man mad,” wrote Darwin. Can we classify these shapes and understand their origins quantitatively?
In biology, there is growing interest in and ability to quantify growth and form in the context of the size and shape of bacteria and other protists, to understand how polymeric assemblies grow and shrink (in the cytoskeleton), and how cells divide, change size and shape, and move to organize tissues, change their topology and geometry, and link multiple scales and connect biochemical to mechanical aspects of these problems, all in a self-regulated setting.
To understand these questions, we need to describe shape (biomathematics), predict shape (biophysics), and design shape (bioengineering).
For example, in mathematics there are some beautiful links to Nash’s embedding theorem, connections to quasi-conformal geometry, Ricci flows and geometric PDE, to Gromov’s h principle, to geometrical singularities and singular geometries, discrete and computational differential geometry, to stochastic geometry and shape characterization (a la Grenander, Mumford etc.). A nice question here is to use the large datasets (in 4D) and analyze them using ideas from statistical geometry (a la Taylor, Adler) to look for similarities and differences across species during development, and across evolution.
In physics, there are questions of generalizing classical theories to include activity, break the usual Galilean invariance, as well as isotropy, frame indifference, homogeneity, and create both agent (cell)-based and continuum theories for ordered, active machines, linking statistical to continuum mechanics, and understanding the instabilities and patterns that arise. Active generalizations of liquid crystals, polar materials, polymers etc. are only just beginning to be explored and there are some nice physical analogs of biological growth/form that are yet to be studied.
The CMSA will be hosting a Workshop on Morphometrics, Morphogenesis and Mathematics from October 22-24, 2018 at the Center of Mathematical Sciences and Applications, located at 20 Garden Street, Cambridge, MA.
The workshop is organized by L. Mahadevan (Harvard), O. Pourquie (Harvard), A. Srivastava (Florida).
Videos of the talks
Confirmed Speakers:

Arkhat Abzhanov, Imperial College
Siobhan Braybrook, UCLA
Cassandra Extavour, Harvard
Anjali Goswami, University College London
David Gu, Stony Brook
Jukka Jernvall, Helsinki
Eric Klassen, Florida State
Sayan Mukherjee, Duke
Peter Olver, U Minnesota
Nipam Patel, Berkeley
Stephanie Pierce, Harvard
Karen Sears, UCLA
Alain Trouve, ENS-Cachan, France
Laurent Younes, Johns Hopkins

F-Theory Workshop
2018-09-29 08:30 - 2018-09-30 15:00
The CMSA hosted an F-Theory workshop September 29-30, 2018. The workshop was held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA.
Youtube Playlist
Organizers:

Paolo Aluffi (Florida State)
Lara B. Anderson (Virginia Tech)
Mboyo Esole (Northeastern)
Shing-Tung Yau (Harvard)

Speakers:

Mirjam Cvetic, University of Pennsylvania
Tommaso de Fernex, University of Utah
James Gray, Virginia Tech
Jonathan Heckman, University of Pennsylvania
Monica Kang, Harvard University
Sándor Kovács, University of Washington
Anatoly Libgober, UIC
Matilde Marcolli, Caltech, University of Toronto, and Perimeter Institute
Washington Taylor, MIT
Cumrun Vafa, Harvard University

Kickoff Workshop on Topology and Quantum Phases of Matter
2018-08-27 09:20 - 2018-08-28 15:15
On August 27-28, 2018, the CMSA will be hosting a Kickoff workshop on Topology and Quantum Phases of Matter. New ideas rooted in topology have recently had a big impact on condensed matter physics, and have highlighted new connections with high energy physics, mathematics and quantum information theory. Additionally, these ideas have found applications in the design of photonic systems and of materials with novel mechanical properties. The aim of this program will be to deepen these connections by fostering discussion and seeding new collaborations within and across disciplines.
This workshop is a part of the CMSA’s program on Program on Topological Aspects of Condensed Matter, and will be the first of two workshops, in addition to a visitor program and seminars.
The workshop will be held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA.
Speakers:

Zhen Bi, MIT
Meng Cheng, Yale
Dima Feldman, Brown
Dominic Else, UCSB
Liang Fu, MIT
Fabian Grusdt, Harvard
Ying Fei Gu, Harvard
Bert Halperin, Harvard
Anton Kapustin, Caltech
Patrick Lee, MIT
L. Mahadevan, Harvard
Brad Marston, Brown
Max Metlitski, MIT
Emil V. Prodan, Yeshiva
Achim Rosch, University of Cologne
Mathias Scheurer, Harvard
Marin Soljacic, MIT
X. G. Wen, MIT
Cenke Xu, UCSB
Frank Zhang, Cornell

On the fibration structure of known Calabi-Yau threefolds
2018-04-13 16:30 - 17:30
Speaker: Washington Tayor (MIT)
Title: On the fibration structure of known Calabi-Yau threefolds
Abstract: In recent years, there is increasing evidence from a variety of directions, including the physics of F-theory and new generalized CICY constructions, that a large fraction of known Calabi-Yau manifolds have a genus one or elliptic fibration. In this talk I will describe recent work with Yu-Chien Huang on a systematic analysis of the fibration structure of known toric hypersurface Calabi-Yau threefolds. Among other results, this analysis shows that every known Calabi-Yau threefold with either Hodge number exceeding 150 is genus one or elliptically fibered, and suggests that the fraction of Calabi-Yau threefolds that are not genus one or elliptically fibered decreases roughly exponentially with h_{11}. I will also make some comments on the connection with the structure of triple intersection numbers in Calabi-Yau threefolds.

Graph Structure in Polynomial Systems: Chordal Networks
2018-04-11 16:30 - 17:30
Speaker: Pablo Parillo (MIT)
Title: Graph Structure in Polynomial Systems: Chordal Networks
Abstract: The sparsity structure of a system of polynomial equations or an optimization problem can be naturally described by a graph summarizing the interactions among the decision variables. It is natural to wonder whether the structure of this graph might help in computational algebraic geometry tasks (e.g., in solving the system). In this lecture we will provide a gentle introduction to this area, focused on the key notions of chordality and treewidth, which are of great importance in related areas such as numerical linear algebra, database theory, constraint satisfaction, and graphical models. In particular, we will discuss “chordal networks”, a novel representation of structured polynomial systems that provides a computationally convenient decomposition of a polynomial ideal into simpler (triangular) polynomial sets, while maintaining its underlying graphical structure. As we will illustrate through examples from different application domains, algorithms based on chordal networks can significantly outperform existing techniques. Based on joint work with Diego Cifuentes (MIT).

Workshop on Coding and Information Theory
2018-04-09 09:00 - 2018-04-13 15:30
The workshop on coding and information theory will take place April 9-13, 2018 at the Center of Mathematical Sciences and Applications, located at 20 Garden Street, Cambridge, MA.
This workshop will focus on new developments in coding and information theory that sit at the intersection of combinatorics and complexity, and will bring together researchers from several communities — coding theory, information theory, combinatorics, and complexity theory — to exchange ideas and form collaborations to attack these problems.
Squarely in this intersection of combinatorics and complexity, locally testable/correctable codes and list-decodable codes both have deep connections to (and in some cases, direct motivation from) complexity theory and pseudorandomness, and recent progress in these areas has directly exploited and explored connections to combinatorics and graph theory. One goal of this workshop is to push ahead on these and other topics that are in the purview of the year-long program. Another goal is to highlight (a subset of) topics in coding and information theory which are especially ripe for collaboration between these communities. Examples of such topics include polar codes; new results on Reed-Muller codes and their thresholds; coding for distributed storage and for DNA memories; coding for deletions and synchronization errors; storage capacity of graphs; zero-error information theory; bounds on codes using semidefinite programming; tensorization in distributed source and channel coding; and applications of information-theoretic methods in probability and combinatorics. All these topics have attracted a great deal of recent interest in the coding and information theory communities, and have rich connections to combinatorics and complexity which could benefit from further exploration and collaboration.
Participation: The workshop is open to participation by all interested researchers, subject to capacity.
A list of lodging options convenient to the Center can also be found on our recommended lodgings page.
Confirmed participants include:

Emmanuel Abbe, Princeton University
Simeon Ball, Universitat Politècnica de Catalunya
Boris Bukh, Carnegie Mellon University
Mahdi Cheraghchi, Imperial College London
Sivakanth Gopi, Princeton University
Elena Grigorescu, University of Purdue
Hamed Hassani, University of Pennsylvania
Navin Kashyap, Indian Institute of Science
Young-Han Kim, University of California, San Diego
Swastik Kopparty, Rutgers University
Nati Linial, Hebrew University of Jerusalem
Shachar Lovett, University of California, San Diego
William Martin, Worcester Polytechnic Institute
Arya Mazumdar, University of Massachusetts at Amherst
Or Meir, University of Haifa
Olgica Milenkovic, ECE Illinois
Chandra Nair, Chinese University of Hong Kong
Yuval Peres, Microsoft Research
Yury Polyanskiy, Massachusetts Institute of Technology
Maxim Raginsky, University of Illinois at Urbana-Champaign
Sankeerth Rao Karingula, UC San Diego
Ankit Singh Rawat, MIT
Noga Ron-Zewi, University of Haifa
Ron Roth, Israel Institute of Technology
Atri Rudra, State University of New York, Buffalo
Alex Samorodnitsky, Hebrew University of Jerusalem
Itzhak Tamo, Tel Aviv University
Amnon Ta-Shma, Tel Aviv University
Himanshu Tyagi, Indian Institute of Science
David Zuckerman, University of Texas at Austin

Simons Collaboration Workshop, April 5-7, 2018
2018-04-05 09:00 - 2018-04-07 17:00
The CMSA will be hosting a three-day Simons Collaboration Workshop on Homological Mirror Symmetry and Hodge Theory on April 5-7, 2018. The workshop will be held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA.
Please click here to register for this event. We have space for up to 30 registrants on a first come, first serve basis.
We may be able to provide some financial support for grad students and postdocs interested in this event. If you are interested in funding, please send a letter of support from your mentor to Hansol Hong.
Confirmed Speakers:

Jacob Bourjaily (Niels Bohr Institute)
Mandy Cheung (Havard University)
Tristan Collins (Harvard University)
Yoosik Kim (Boston University)
Yu-Shen Lin (Harvard University)
Cheuk-Yu Mak (Cambridge University)
Yu Pan (MIT)
Mauricio Romo (Tsinghua University)
Shu-Heng Shao (IAS)
Zack Sylvan (Columbia University)
Dmitry Vaintrob (IAS)

Black Holes and Naked Singularities
2018-04-04 16:30
Speaker: Ramesh Narayan, Department of Astronomy, Harvard University
Title: Black Holes and Naked Singularities
Abstract: Black Hole solutions in General Relativity contain Event Horizons and Singularities. Astrophysicists have discovered two populations of black hole candidates in the Universe: stellar-mass objects with masses in the range 5 to 30 solar masses, and supermassive objects with masses in the range million to several billion solar masses. There is considerable evidence that these objects have Event Horizons. It thus appears that astronomical black hole candidates are true Black Holes. Direct evidence for Singularities is much harder to obtain since, at least in the case of Black Holes, the Singularities are hidden inside the Event Horizon. However, General Relativity also permits Naked Singularities which are visible to external observers. Toy Naked Singularity models have been constructed, and some observational features of accretion flows in these spacetimes have been worked out.

A Mean Field View of the Landscape of Two-Layers Neural Networks
2018-03-28 16:30 - 17:30
Speaker: Andrea Montanari (Stanford)
Title: A Mean Field View of the Landscape of Two-Layers Neural Networks
Abstract: Multi-layer neural networks are among the most powerful models in machine learning and yet, the fundamental reasons for this success defy mathematical understanding. Learning a neural network requires to optimize a highly non-convex and high-dimensional objective (risk function), a problem which is usually attacked using stochastic gradient descent (SGD). Does SGD converge to a global optimum of the risk or only to a local optimum? In the first case, does this happen because local minima are absent, or because SGD somehow avoids them? In the second, why do local minima reached by SGD have good generalization properties? We consider a simple case, namely two-layers neural networks, and prove that –in a suitable scaling limit– the SGD dynamics is captured by a certain non-linear partial differential equation. We then consider several specific examples, and show how the asymptotic description can be used to prove convergence of SGD to network with nearly-ideal generalization error. This description allows to ‘average-out’ some of the complexities of the landscape of neural networks, and can be used to capture some important variants of SGD as well. [Based on joint work with Song Mei and Phan-Minh Nguyen]

Workshop on Geometry, Imaging, and Computing
2018-03-24 09:00 - 2018-03-26 18:15
On March 24-26, The Center of Mathematical Sciences and Applications will be hosting a workshop on Geometry, Imaging, and Computing, based off the journal of the same name. The workshop will take place in CMSA building, G10.
The organizing committee consists of Yang Wang (HKUST), Ronald Lui (CUHK), David Gu (Stony Brook), and Shing-Tung Yau (Harvard).
Confirmed Speakers:

Jianfeng Cai (HKUST)
Shikui Chen (Stony Brook)
Jerome Darbon (Brown University)
Laurent Demanet (MIT)
David Gu (Stony Brook)
Monica Hurdal (Florida State University)
Rongjie Lai (RPI)
Yue Lu (Harvard)
Ronald Lok Ming Lui (CUHK)
Lakshminarayanan Mahadevan (Harvard)
Eric Miller (Tufts)
Ashley Prater (AFOSR)
Lixin Shen (Syracuse University)
Allen Tannenbaum (Stony Brook)
Guowei Wei (Michigan State)
Stephen Wong (Houston Methodist)
Jun Zhang (University of Michigan, Ann Arbor)
Song Zhang (Purdue University)
Hongkai Zhao (University of California, Irvine)

Essential concepts of Causal inference—a remarkable history
2018-02-21 16:30 - 17:30
Speaker: Don Rubin (Harvard Statistics)
Title: Essential concepts of Causal inference—a remarkable history
Abstract: I believe that a deep understanding of cause and effect, and how to estimate causal effects from data, complete with the associated mathematical notation and expressions, only evolved in the twentieth century. The crucial idea of randomized experiments was apparently first proposed in 1925 in the context of agricultural field trails but quickly moved to be applied also in studies of animal breeding and then in industrial manufacturing. The conceptual understanding seemed to be tied to ideas that were developing in quantum mechanics. The key ideas of randomized experiments evidently were not applied to studies of human beings until the 1950s, when such experiments began to be used in controlled medical trials, and then in social science — in education and economics. Humans are more complex than plants and animals, however, and with such trials came the attendant complexities of non-compliance with assigned treatment and the occurrence of “hawthorne” and placebo effects. The formal application of the insights from earlier simpler experimental settings to more complex ones dealing with people, started in the 1970s and continue to this day, and include the bridging of classical mathematical ideas of experimentation, including fractional replication and geometrical formulations from the early twentieth century, with modern ideas that rely on powerful computing to implement aspects of design and analysis.

Workshop on Probabilistic and Extremal Combinatorics
2018-02-05 09:00 - 2018-02-09 17:00
The workshop on Probabilistic and Extremal Combinatorics will take place February 5-9, 2018 at the Center of Mathematical Sciences and Applications, located at 20 Garden Street, Cambridge, MA.
Extremal and Probabilistic Combinatorics are two of the most central branches of modern combinatorial theory. Extremal Combinatorics deals with problems of determining or estimating the maximum or minimum possible cardinality of a collection of finite objects satisfying certain requirements. Such problems are often related to other areas including Computer Science, Information Theory, Number Theory and Geometry. This branch of Combinatorics has developed spectacularly over the last few decades. Probabilistic Combinatorics can be described informally as a (very successful) hybrid between Combinatorics and Probability, whose main object of study is probability distributions on discrete structures.
There are many points of interaction between these fields. There are deep similarities in methodology. Both subjects are mostly asymptotic in nature. Quite a few important results from Extremal Combinatorics have been proven applying probabilistic methods, and vice versa. Such emerging subjects as Extremal Problems in Random Graphs or the theory of graph limits stand explicitly at the intersection of the two fields and indicate their natural symbiosis.
The symposia will focus on the interactions between the above areas. These topics include Extremal Problems for Graphs and Set Systems, Ramsey Theory, Combinatorial Number Theory, Combinatorial Geometry, Random Graphs, Probabilistic Methods and Graph Limits.
Participation: The workshop is open to participation by all interested researchers, subject to capacity.
Confirmed participants include:

Jozsef Balogh, University of Illinois, Urbana
Fan Chung (Graham), University of California, San Diego
Asaf Ferber, Massachusetts Institute of Technology
Jacob Fox, Stanford Unviersity
David Gamarnik, Massachusetts Institute of Technology
Penny Haxell, University of Waterloo
Hao Huang, Emory University
Jeff Kahn, Rutgers University
Peter Keevash, Oxford University
Michael Krivelevich, Tel Aviv University
Daniela Kühn, University of Birmingham
Shoham Letzer, ITS Zürich
Shachar Lovett, University of California, San Diego
Eyal Lubetzky, Courant Institute
Rob Morris, IMPA
Bhargav Narayanan, Rutgers University
Deryk Osthus, University of Birmingham
Janos Pach, NYU
Yuval Peres, Microsoft Redmond
Alexey Pokryovskyi, ETH Zürich
Wojciech Samotij, Tel Aviv University
Lisa Sauermann, Stanford University
Mathias Schacht, University of Hamburg
Alexander Scott, University of Oxford
Asaf Shapira, Tel Aviv University
Jozef Skokan, London School of Economics
Joel Spencer, New York University
Angelika Steger, ETH Zurich
Jacques Verstraete, University of California, San Diego
Yufei Zhao, Massachusetts Institute of Technology
David Zuckerman, University of Texas at Austin

Co-organizers of this workshop include Benny Sudakov and David Conlon. More details about this event, including participants, will be updated soon.

Workshop on Algebraic Methods in Combinatorics
2017-11-13 09:00 - 2017-11-17 16:00
The workshop on Algebraic Methods in Combinatorics will take place November 13-17, 2017 at the Center of Mathematical Sciences and Applications, located at 20 Garden Street, Cambridge, MA.
The main focus of the workshop is the application of algebraic method to study problems in combinatorics. In recent years there has been a large number of results in which the use of algebraic technique has resulted in significant improvements to long standing open problems. Such problems include the finite field Kakeya problem, the distinct distance problem of Erdos and, more recently, the cap-set problem. The workshop will include talks on all of the above mentioned problem as well as on recent development in related areas combining combinatorics and algebra.
Confirmed participants include:

Abdul Basit, Rutgers
Boris Bukh, Carnegie Mellon University
Pete L. Clark, University of Georgia
David Conlon, University of Oxford
Frank de Zeeuw, EPFL
Thao Thi Thu Do, MIT
Noam Elkies, Harvard University
Jordan Ellenberg, University of Wisconsin
Dion Gijswijt, Delft Institute of Technology
Sivankanth Gopi, Princeton University
Venkatesan Guruswami, Carnegie Mellon University
Marina Iliopoulou, University of California, Berkeley
Robert Kleinberg, Cornell University
Michael Krivelevich, Tel Aviv University
Vsevelod Lev, University of Haifa at Oranim
László Miklós Lovász, UCLA
Ben Lund, Rutgers
Péter Pach, Budapest University of Technology and Economics
János Pach, New York University
Zuzana Patáková, Institute of Science and Technology Austria
Orit Raz, Institute for Advanced Study
Oliver Roche-Newton, Johannes Kepler University
Misha Rudnev, University of Bristol
Adam Sheffer, California Institute of Technology
Amir Shpilka, Tel-Aviv University
Noam Solomon, Harvard CMSA
Jozsef Solymosi, University of British Columbia
Benny Sudakov, ETH, Zurich
Andrew Suk, University of California, San Diego
Tibor Szabó, Freie Universität Berlin
Chris Umans, California Institute of Technology
Avi Wigderson, Princeton University
Josh Zahl, University of British Columbia

Co-organizers of this workshop include Zeev Dvir, Larry Guth, and Shubhangi Saraf.
Monday, Nov. 13

Time
Speaker
Title/Abstract

9:00-9:30am
Breakfast

9:30-10:30am
Video
Jozsef Solymosi

On the unit distance problem
Abstract: Erdos’ Unit Distances conjecture states that the maximum number of unit distances determined by n points in the plane is almost linear, it is O(n^{1+c}) where c goes to zero as n goes to infinity. In this talk I will survey the relevant results and propose some questions which would imply that the maximum number of unit distances is o(n^{4/3}).

10:30-11:00am
Coffee Break

11:00-12:00pm
Video

Orit Raz
Intersection of linear subspaces in R^d and instances of the PIT problem
Abstract: In the talk I will tell about a new deterministic, strongly polynomial time algorithm which can be viewed in two ways. The first is as solving a derandomization problem, providing a deterministic algorithm to a new special case of the PIT (Polynomial Identity Testing) problem. The second is as computing the dimension of the span of a collection of flats in high dimensional space. The talk is based on a joint work with Avi Wigderson.

12:00-1:30pm
Lunch

1:30-2:30pm
Video
Andrew Hoon Suk

Ramsey numbers: combinatorial and geometric
Abstract: In this talk, I will discuss several results on determining the tower growth rate of Ramsey numbers arising in combinatorics and in geometry. These results are joint work with David Conlon, Jacob Fox, Dhruv Mubayi, Janos Pach, and Benny Sudakov.

2:30-3:00pm
Coffee Break

3:00-4:00pm
Video
Josh Zahl

Cutting curves into segments and incidence geometry

4:00-6:00pm
Welcome Reception

Tuesday, Nov. 14

Time
Speaker
Title/Abstract

9:00-9:30am
Breakfast

9:30-10:30am
Video
Péter Pál Pach

Polynomials, rank and cap sets
Abstract: In this talk we will look at a new variant of the polynomial method which was first used to prove that sets avoiding 3-term arithmetic progressions in groups like $mathbb{Z}_4^n$ and $mathbb{F}_q^n$ are exponentially small (compared to the size of the group). We will discuss lower and upper bounds for the size of the extremal subsets and mention further applications of the method.

10:30-11:00am
Coffee Break

11:00-12:00pm
Jordan Ellenberg

The Degeneration Method
Abstract: In algebraic geometry, a very popular way to study (nice, innocent, nonsingular) varieties is to degenerate them to (weird-looking, badly singular, nonreduced) varieties (which are actually not even varieties but schemes.) I will talk about some results in combinatorics using this approach (joint with Daniel Erman) and some ideas for future applications of the method.

12:00-1:30pm
Lunch

1:30-2:30pm
Video
Larry Guth
The polynomial method in Fourier analysis
Abstract: This will be a survey talk about how the polynomial method helps to understand problems in Fourier analysis. We will review some applications of the polynomial method to problems in combinatorial geometry. Then we’ll discuss some problems in Fourier analysis, explain the analogy with combinatorial problems, and discuss how to adapt the polynomial method to the Fourier analysis setting.

2:30-3:00pm
Coffee Break

3:00-4:00pm
Open Problem

Wednesday, Nov. 15

Time
Speaker
Title/Abstract

9:00-9:30am
Breakfast

9:30-10:30am

Avi Wigderson

The “rank method” in arithmetic complexity: Lower bounds and barriers to lower bounds
Abstract: Why is it so hard to find a hard function? No one has a clue! In despair, we turn to excuses called barriers. A barrier is a collection of lower bound techniques, encompassing as much as possible from those in use, together with a proof that these techniques cannot prove any lower bound better than the state-of-art (which is often pathetic, and always very far from what we expect for complexity of random functions).
In the setting of Boolean computation of Boolean functions (where P vs. NP is the central open problem), there are several famous barriers which provide satisfactory excuses, and point to directions in which techniques may be strengthened.
In the setting of Arithmetic computation of polynomials and tensors (where VP vs. VNP is the central open problem) we have no satisfactory barriers, despite some recent interesting attempts.
This talk will describe a new barrier for the Rank Method in arithmetic complexity, which encompass most lower bounds in this field. It also encompass most lower bounds on tensor rank in algebraic geometry (where the the rank method is called Flattening).
I will describe the rank method, explain how it is used to prove lower bounds, and then explain its limits via the new barrier result. As an example, it shows that while the best lower bound on the tensor rank of any explicit 3-dimensional tensor of side n (which is achieved by a rank method) is 2n, no rank method can prove a lower bound which exceeds 8n
(despite the fact that a random such tensor has rank quadratic in n).
No special background knowledge is assumed. The audience is expected to come up with new lower bounds, or else, with new excuses for their absence.

10:30-11:00am
Coffee Break

11:00-12:00pm
Video
Venkat Guruswami

Subspace evasion, list decoding, and dimension expanders
Abstract: A subspace design is a collection of subspaces of F^n (F = finite field) most of which are disjoint from every low-dimensional subspace of F^n. This notion was put forth in the context of algebraic list decoding where it enabled the construction of optimal redundancy list-decodable codes over small alphabets as well as for error-correction in the rank-metric. Explicit subspace designs with near-optimal parameters have been constructed over large fields based on polynomials with structured roots. (Over small fields, a construction via cyclotomic function fields with slightly worse parameters is known.) Both the analysis of the list decoding algorithm as well as the subspace designs crucially rely on the *polynomial method*.
Subspace designs have since enabled progress on linear-algebraic analogs of Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In particular, they yield an explicit construction of constant-degree dimension expanders over large fields. While constructions of such dimension expanders are known over any field, they are based on a reduction to a highly non-trivial form of vertex expanders called monotone expanders. In contrast, the subspace design approach is simpler and works entirely within the linear-algebraic realm. Further, in recent (ongoing) work, their combination with rank-metric codes yields dimension expanders with expansion proportional to the degree.
This talk will survey these developments revolving around subspace designs, their motivation, construction, analysis, and connections.
(Based on several joint works whose co-authors include Chaoping Xing, Swastik Kopparty, Michael Forbes, Nicolas Resch, and Chen Yuan.)

12:00-1:30pm
Lunch

1:30-2:30pm

David Conlon

Finite reflection groups and graph norms
Abstract: For any given graph $H$, we may define a natural corresponding functional $|.|_H$. We then say that $H$ is norming if $|.|_H$ is a semi-norm. A similar notion $|.|_{r(H)}$ is defined by $| f |_{r(H)} := | | f | |_H$ and $H$ is said to be weakly norming if $|.|_{r(H)}$ is a norm. Classical results show that weakly norming graphs are necessarily bipartite. In the other direction, Hatami showed that even cycles, complete bipartite graphs, and hypercubes are all weakly norming. Using results from the theory of finite reflection groups, we identify a much larger class of weakly norming graphs. This result includes all previous examples of weakly norming graphs and adds many more. We also discuss several applications of our results. In particular, we define and compare a number of generalisations of Gowers’ octahedral norms and we prove some new instances of Sidorenko’s conjecture. Joint work with Joonkyung Lee.

2:30-3:00pm
Coffee Break

3:00-4:00pm
Video
Laszlo Miklós Lovasz

Removal lemmas for triangles and k-cycles.
Abstract: Let p be a fixed prime. A k-cycle in F_p^n is an ordered k-tuple of points that sum to zero; we also call a 3-cycle a triangle. Let N=p^n, (the size of F_p^n). Green proved an arithmetic removal lemma which says that for every k, epsilon>0 and prime p, there is a delta>0 such that if we have a collection of k sets in F_p^n, and the number of k-cycles in their cross product is at most a delta fraction of all possible k-cycles in F_p^n, then we can delete epsilon times N elements from the sets and remove all k-cycles. Green posed the problem of improving the quantitative bounds on the arithmetic triangle removal lemma, and, in particular, asked whether a polynomial bound holds. Despite considerable attention, prior to our work, the best known bound for any k, due to Fox, showed that 1/delta can be taken to be an exponential tower of twos of height logarithmic in 1/epsilon (for a fixed k).
In this talk, we will discuss recent work on Green’s problem. For triangles, we prove an essentially tight bound for Green’s arithmetic triangle removal lemma in F_p^n, using the recent breakthroughs with the polynomial method. For k-cycles, we also prove a polynomial bound, however, the question of the optimal exponent is still open.
The triangle case is joint work with Jacob Fox, and the k-cycle case with Jacob Fox and Lisa Sauermann.

Thursday, Nov. 16

Time
Speaker
Title/Abstract

9:00-9:30am
Breakfast

9:30-10:30am
Video
Janos Pach
Let’s talk about multiple crossings
Abstract: Let k>1 be a fixed integer. It is conjectured that any graph on n vertices that can be drawn in the plane without k pairwise crossing edges has O(n) edges. Two edges of a hypergraph cross each other if neither of them contains the other, they have a nonempty intersection, and their union is not the whole vertex set. It is conjectured that any hypergraph on n vertices that contains no k pairwise crossing edges has at most O(n) edges. We discuss the relationship between the above conjectures and explain some partial answers, including a recent result of Kupavskii, Tomon, and the speaker, improving a 40 years old bound of Lomonosov.

10:30-11:00am
Coffee Break

11:00-12:00pm
Video
Misha Rudnev

Few products, many sums
Abstract: This is what I like calling “weak ErdH os-Szemer’edi conjecture”, still wide open over the reals and in positive characteristic. The talk will focus on some recent progress, largely based on the ideas of I. D. Shkredov over the past 5-6 years of how to use linear algebra to get the best out of the Szemer’edi-Trotter theorem for its sum-product applications. One of the new results is strengthening (modulo the log term hidden in the $lesssim$ symbol) the textbook Elekes inequality
$$
|A|^{10} ll |A-A|^4|AA|^4
$$
to
$$|A|^{10}lesssim |A-A|^3|AA|^5.$$
The other is the bound
$$E(H) lesssim |H|^{2+frac{9}{20}}$$ for additive energy of sufficiently small multiplicative subgroups in $mathbb F_p$.

12:00-1:30pm
Lunch

1:30-2:30pm
Video
Adam Sheffer

Geometric Energies: Between Discrete Geometry and Additive Combinatorics
Abstract: We will discuss the rise of geometric variants of the concept of Additive energy. In recent years such variants are becoming more common in the study of Discrete Geometry problems. We will survey this development and then focus on a recent work with Cosmin Pohoata. This work studies geometric variants of additive higher moment energies, and uses those to derive new bounds for several problems in Discrete Geometry.

2:30-3:00pm
Coffee Break

3:00-4:00pm
Video
Boris Bukh

Ranks of matrices with few distinct entries
Abstract: Many applications of linear algebra method to combinatorics rely on the bounds on ranks of matrices with few distinct entries and constant diagonal. In this talk, I will explain some of these application. I will also present a classification of sets L for which no low-rank matrix with entries in L exists.

Friday, Nov. 17

Time
Speaker
Title/Abstract

9:00-9:30am
Breakfast

9:30-10:30am
Video
Benny Sudakov

Submodular minimization and set-systems with restricted intersections
Abstract: Submodular function minimization is a fundamental and efficiently solvable problem class in combinatorial optimization with a multitude of applications in various fields. Surprisingly, there is only very little known about constraint types under which it remains efficiently solvable. The arguably most relevant non-trivial constraint class for which polynomial algorithms are known are parity constraints, i.e., optimizing submodular function only over sets of odd (or even) cardinality. Parity constraints capture classical combinatorial optimization problems like the odd-cut problem, and they are a key tool in a recent technique to efficiently solve integer programs with a constraint matrix whose subdeter-minants are bounded by two in absolute value.
We show that efficient submodular function minimization is possible even for a significantly larger class than parity constraints, i.e., over all sets (of any given lattice) of cardinality r mod m, as long as m is a constant prime power. To obtain our results, we combine tools from Combinatorial Optimization, Combinatorics, and Number Theory. In particular, we establish an interesting connection between the correctness of a natural algorithm, and the non-existence of set systems with specific intersection properties.
Joint work with M. Nagele and R. Zenklusen

10:30-11:00am
Coffee Break

11:00-12:00pm
Video
Robert Kleinberg

Explicit sum-of-squares lower bounds via the polynomial method
Abstract: The sum-of-squares (a.k.a. Positivstellensatz) proof system is a powerful method for refuting systems of multivariate polynomial inequalities, i.e. proving that they have no solutions. These refutations themselves involve sum-of-squares (sos) polynomials, and while any unsatisfiable system of inequalities has a sum-of-squares refutation, the sos polynomials involved might have arbitrarily high degree. However, if a system admits a refutation where all polynomials involved have degree at most d, then the refutation can be found by an algorithm with running time polynomial in N^d, where N is the combined number of variables and inequalities in the system.
Low-degree sum-of-squares refutations appear throughout mathematics. For example, the above proof search algorithm captures as a special case many a priori unrelated algorithms from theoretical computer science; one example is Goemans and Williamson’s algorithm to approximate the maximum cut in a graph. Specialized to extremal graph theory, they become equivalent to flag algebras. They have also seen practical use in robotics and optimal control.
Therefore, it is of interest to identify “hard” systems of low-degree polynomial inequalities that have no solutions but also have no low-degree sum-of-squares refutations. Until recently, the only known examples were either not explicit (i.e., known to exist by non-constructive means such as the probabilistic method) or not robust (i.e., a system is constructed which is not refutable by degree d sos polynomials, but becomes refutable when perturbed by an amount tending to zero with d). We present a new family of instances derived from the cap-set problem, and we show a super-constant lower bound on the degree of its sum-of-squares refutations. Our instances are both explicit and robust.
This is joint work with Sam Hopkins.

12:00-1:30pm
Lunch

Events,Past Events,Programs

Workshop on Additive Combinatorics, Oct. 2-6, 2017
2017-10-02 09:00 - 2017-10-06 16:00
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.
Additive 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:

The first sensible bounds for Szemerédi’s theorem on progressions (Gowers);
Linear patterns in the primes (Green, Tao, Ziegler);
Construction of expanding sets in groups and expander graphs (Bourgain, Gamburd);
The Kakeya Problem in Euclidean harmonic analysis (Bourgain, Katz, Tao).

Ideas and techniques from additive combinatorics have also had an impact in theoretical computer science, for example

Constructions of pseudorandom objects (eg. extractors and expanders);
Constructions of extremal objects (eg. BCH codes);
Property testing (eg. testing linearity);
Algebraic algorithms (eg. matrix multiplication).

The 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.
Confirmed participants include:

Arnab Bhattacharyya (Indian Institute of Science)
Thomas Bloom (University of Bristol)
Jop Briët (Centrum Wiskunde & Informatica, Amsterdam)
Mei-Chu Chang (University of California, Riverside)
Noam Elkies (Harvard University)
Asaf Ferber (MIT)
Jacob Fox (Stanford University)
Shafi Goldwasser (MIT)
Elena Grigorescu (Purdue University)
Hamed Hatami (McGill University)
Pooya Hatami (Institute for Advanced Study)
Kaave Hosseini (University of California, San Diego)
Guy Kindler (Hebrew University of Jerusalem)
Vsevolod Lev (University of Haifa at Oranim)
Sean Prendiville (University of Manchester)
Ronitt Rubinfeld (MIT)
Will Sawin (ETH Zürich)
Fernando Shao (Oxford University)
Olof Sisask (KTH Royal Institute of Technology)
Madhur Tulsiani (University of Chicago)
Julia Wolf (University of Bristol)
Emanuele Viola (Northeastern University)
Yufei Zhao (MIT)

Co-organizers of this workshop include Ben Green, Swastik Kopparty, Ryan O’Donnell, Tamar Ziegler.
Monday, October 2

Time
Speaker
Title/Abstract

9:00-9:30am
Breakfast

9:30-10:20am
Jacob Fox
Tower-type bounds for Roth’s theorem with popular differences
Abstract: 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.
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.

10:20-11:00am
Coffee Break

11:00-11:50am
Yufei Zhao
Tower-type bounds for Roth’s theorem with popular differences
Abstract: 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.

12:00-1:30pm
Lunch

1:30-2:20pm
Jop Briët
Locally decodable codes and arithmetic progressions in random settings
Abstract: 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.
Joint work with Sivakanth Gopi

2:20-3:00pm
Coffee Break

3:00-3:50pm
Fernando Shao

Large deviations for arithmetic progressions
Abstract: 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.

4:00-6:00pm
Welcome Reception

Tuesday, October 3

Time
Speaker
Title/Abstract

9:00-9:30am
Breakfast

9:30-10:20am
Emanuele Viola
Interleaved group products
Authors: Timothy Gowers and Emanuele Viola
Abstract: 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.
These results have applications in computer science, which is the area where they were first sought by Miles and Viola (2013).

10:20-11:00am
Coffee Break

11:00-11:50am
Vsevolod Lev
On Isoperimetric Stability
Abstract: 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 $cin(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.
As 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.
We also prove, as an auxiliary result, the following estimate of possible independent interest: if $Asubseteq{mathbb Z}^n$ is a finite, non-empty downset, then, denoting by $w(z)$ the number of non-zero components of the vector $zinmathbb{Z}^n$, we have $$ frac1{|A|} sum_{ain A} w(a) le frac12\, log_2 |A|. $$

12:00-1:30pm
Lunch

1:30-2:20pm
Elena Grigorescu
NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem
Abstract: 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.
Joint work with Venkata Gandikota and Badih Ghazi.

2:20-3:00pm
Coffee Break

3:00-3:50pm
Sean Prendiville
Partition regularity of certain non-linear Diophantine equations.
Abstract: 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.

Wednesday, October 4

Time
Speaker
Title/Abstract

9:00-9:30am
Breakfast

9:30-10:20am
Olof Sisask
Bounds on capsets via properties of spectra
Abstract: 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.
Joint work with Thomas Bloom.

10:20-11:00am
Coffee Break

11:00-11:50am
Thomas Bloom
Bounds on capsets via properties of spectra
This is a continuation of the previous talk by Olof Sisask.

12:00-1:30pm
Lunch

1:30-2:20pm
Hamed Hatami
Polynomial method and graph bootstrap percolation
Abstract: 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.

2:20-3:00pm
Coffee Break

3:00-3:50pm
Arnab Bhattacharyya
Algorithmic Polynomial Decomposition
Abstract: 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.
When 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.
Joint work with Pooya Hatami, Chetan Gupta and Madhur Tulsiani.

Thursday, October 5

Time
Speaker
Title/Abstract

9:00-9:30am
Breakfast

9:30-10:20am
Madhur Tulsiani
Higher-order Fourier analysis and approximate decoding of Reed-Muller codes
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.
I 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.
Based on joint works with Arnab Bhattacharyya, Eli Ben-Sasson, Pooya Hatami, Noga Ron-Zewi and Julia Wolf.

10:20-11:00am
Coffee Break

11:00-11:50am
Julia Wolf
Stable arithmetic regularity
The 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.
Our 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.
This is joint work with Caroline Terry.

12:00-1:30pm
Lunch

1:30-2:20pm
Will Sawin

Constructions of Additive Matchings
Abstract: 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.

2:20-3:00pm
Coffee Break

3:00-3:50pm
Mei-Chu Chang
Arithmetic progressions in multiplicative groups of finite fields
Abstract: 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.

Friday, October 6

Time
Speaker
Title/Abstract

9:00-9:30am
Breakfast

9:30-10:20am
Asaf Ferber
On a resilience version of the Littlewood-Offord problem
Abstract: 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.
Joint with: Afonso Bandeira (NYU) and Matthew Kwan (ETH, Zurich).

10:20-11:00am
Coffee Break

11:00-11:50am
Kaave Hosseini
Protocols for XOR functions and Entropy decrement
Abstract: 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.
This relies on a novel technique of entropy decrement combined with Sanders’ Bogolyubov-Ruzsa lemma.
Joint work with Hamed Hatami and Shachar Lovett

12:00-1:30pm
Lunch

1:30-2:20pm
Guy Kindler

From the Grassmann graph to Two-to-Two games
Abstract: 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.
The 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.
These 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.
This is joint work with Irit Dinur, Subhash Khot, Dror Minzer, and Muli Safra.

Events,Past Events

4-18-2017 Social Science Applications Forum
2017-04-18 11:00 - 12:00

3-24-2017 Random Matrix & Probability Theory Seminar
2017-03-24 10:00 - 11:00

Special Lecture Series on Donaldson-Thomas and Gromov-Witten Theories
2017-03-08 12:11 - 2017-04-19 12:11
From March 8 to April 19, the Center of Mathematical Sciences and Applications will be hosting a special lecture series on Donaldson-Thomas and Gromov-Witten Theories. Artan Sheshmani (QGM Aarhus and CMSA Harvard) will give eight talks on the topic on Wednesdays and Fridays from 9:00-10:30 am, which will be recorded and promptly available on CMSA’s Youtube Channel.

Mini-school on Nonlinear Equations, December 3-4, 2016
2016-12-03 09:00 - 2016-12-04 17:00
The Center of Mathematical Sciences and Applications will be hosting a Mini-school on Nonlinear Equations on December 3-4, 2016. The conference will have speakers and will be hosted at Harvard CMSA Building: Room G10 20 Garden Street, Cambridge, MA 02138.
Speakers:

Cliff Taubes (Harvard University)
Valentino Tosatti (Northwestern University)
Pengfei Guan (McGill University)
Jared Speck (MIT)

Schedule:

December 3rd – Day 1

9:00am – 10:30am
Cliff Taubes, “Compactness theorems in gauge theories”

10:45am – 12:15pm
Valentino Tosatti, “Complex Monge-Ampère Equations”

12:15pm – 1:45pm
LUNCH

1:45pm – 3:15pm
Pengfei Guan, “Monge-Ampère type equations and related geometric problems”

3:30pm – 5:00pm
Jared Speck, “Finite-time degeneration of hyperbolicity without blowup for solutions to quasilinear wave equations”

December 4th – Day 2

9:00am – 10:30am
Cliff Taubes, “Compactness theorems in gauge theories”

10:45am – 12:15pm
Valentino Tosatti, “Complex Monge-Ampère Equations”

12:15pm – 1:45pm
LUNCH

1:45pm – 3:15pm
Pengfei Guan, “Monge-Ampère type equations and related geometric problems”

3:30pm – 5:00pm
Jared Speck, “Finite-time degeneration of hyperbolicity without blowup for solutions to quasilinear wave equations”

* This event is sponsored by National Science Foundation (NSF) and CMSA Harvard University.
