CMSA

Workshop on Probabilistic and Extremal Combinatorics
2018-02-05 09:00 - 2018-02-09 17:00 (America/New_York) | CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
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.

2-2-2018 Mirror Symmetry Seminar
2018-02-02 14:44 | MA

1-29-2018 Mathematical Physics Seminar
2018-01-29 14:42 | MA

01-26-2018 Mirror Symmetry Seminar
2018-01-26 14:37 | MA

Quantum Cohomology, Nakajima Varieties and Quantum groups
2018-01-25 14:21 | MA
During the Spring 2018 Semester Artan Sheshmani (QGM/CMSA) will be teaching a CMSA special lecture series on Quantum Cohomology, Nakajima Vareties and Quantum groups. The lectures will be held Tuesdays and Thursdays beginning January 25th, from 1:00 to 3:00pm in room G10, CMSA Building.
You can watch Prof. Sheshmani describe the series here.
The Syllabus is as follows:

Date………..
Topic
Video/Audio

1-25-2018
Gromov-Witten invariants
Definition, examples via algebraic geometry I
Video / Audio / Combined

*due to technical difficulties the audio and video are split for this lecture.

2-01-2018
Gromov-Witten invariants
Virtual Fundamental Class I (definition)
Video / Audio / Combined

*due to technical difficulties the audio and video are split for this lecture

2-13-2018
Gromov-Witten invariants
Virtual Fundamental Class II (computation in some cases)

2-15-2018
Computing GW invariants
Three level GW classes
Genus zero invariants of the projective plane

2-20-2018
Quantum Cohomology
Small Quantum Cohomology (Definition and Properties) I

2-22-2018
Quantum Cohomology
Small Quantum Cohomology (Definition and Properties) II

2-27-2018
Quantum Cohomology
Big Quantum Cohomology I

3-1-2018
Quantum Cohomology
Big Quantum Cohomology II
GW potential
WDVV equation

3-6-2018
GW invariants via Quantum Cohomology
The Quintic threefold case
The P^2 case

GW invariants via Quantum Cohomology
Dubrovin (quantum) connection

Nakajima varieties
-Algebraic and symplectic reduction

Nakajima varieties
Quasi maps to Nakajima varieties

Quantum cohomology of Nakajima varieties
Small Quantum Cohomology of Hilb^n (C2) I

Quantum cohomology of Nakajima varieties
Small Quantum Cohomology of Hilb^n (C2) II

Quantum cohomology of Nakajima varieties
Small Quantum Cohomology of Hilb^n (C2) III

Quantum cohomology of Nakajima varieties
Big Quantum Cohomology of Hilb^n (C2) I

Quantum cohomology of Nakajima varieties
Big Quantum Cohomology of Hilb^n (C2) II

Quantum cohomology of Nakajima varieties
Big Quantum Cohomology of Hilb^n (C2) III

Quantum cohomology of Nakajima varieties
Big Quantum Cohomology of Hilb^n (C2) IV

Blockchain Conference
2018-01-24 09:00 - 2018-01-25 17:00 | Harvard Science Center, 1 Oxford Street, Cambridge, MA, 02138
On January 24-25, 2019 the Center of Mathematical Sciences will be hosting a conference on distributed-ledger (blockchain) technology. The conference is intended to cover a broad range of topics, from abstract mathematical aspects (cryptography, game theory, graph theory, theoretical computer science) to concrete applications (in accounting, government, economics, finance, management, medicine). The talks will take place in Science Center, Hall D.
https://youtu.be/FyKCCutxMYo
Photos

Speakers:

Joseph Abadi, Princeton University
Benedikt Bunz, Stanford University
Jake Cacciapaglia, Nebula Genomics/Harvard Medical School
Eduardo Castello, Massachusetts Institute of Technology
Alisa DiCaprio, R3
Zhiguo He, University of Chicago
Steven Kou, Boston University
Anne Lafarre, Tilburg University
Jacob Leshno, University of Chicago
Bruce Schneier, Harvard Kennedy School
David Schwartz, Ripple
Elaine Shi, Cornell University/Thunder Research
Hong Wan, NCSU

2018 HMS Focused Lecture Series
2018-01-23 17:00 | MA
As part of their CMSA visitation, HMS focused visitors will be giving lectures on various topics related to Homological Mirror Symmetry throughout the Spring 2018 Semester. The lectures will take place on Tuesdays and Thursdays in the CMSA Building, 20 Garden Street, Room G10.
The schedule will be updated below.

Date
Speaker
Title/Abstract

January 23, 25, 30 and February 1
3-5pm
*Room G10*
Ivan Losev
(Northeastern)
Title: BGG category O: towards symplectic duality
Abstract: We will discuss a very classical topic in the representation theory of semisimple Lie algebras: the Bernstein-Gelfand-Gelfand (BGG) category O. Our aim will be to motivate and state a celebrated result of Beilinson, Ginzburg and Soergel on the Koszul duality for such categories, explaining how to compute characters of simple modules (the Kazhdan-Lusztig theory) along the way. The Koszul duality admits a conjectural generalization (Symplectic duality) that is a Mathematical manifestation of 3D Mirror symmetry. We will discuss that time permitting.
Approximate (optimistic) plan of the lectures:
1) Preliminaries and BGG category O.
2) Kazhdan-Lusztig bases. Beilinson-Bernstein localization theorem.
3) Localization theorem continued. Soergel modules.
4) Koszul algebras and Koszul duality for categories O.
Time permitting: other instances of Symplectic duality.
Prerequisites:
Semi-simple Lie algebras and their finite dimensional representation theory.
Some Algebraic geometry. No prior knowledge of category O/ Geometric
Representation theory is assumed.
Scanned from a Xerox Multifunction Device

February 27,
and March 1
3-5pm
Colin Diemer
(IHES)
Title: Moduli spaces of Landau-Ginzburg models and (mostly Fano) HMS.
Abstract: Mirror symmetry as a general phenomenon is understood to take place near the large complex structure limit resp. large radius limit, and so implicitly involves degenerations of the spaces under consideration. Underlying most mirror theorems is thus a mirror map which gives a local identification of respective A-model and B-model moduli spaces. When dealing with mirror symmetry for Calabi-Yau’s the role of the mirror map is well-appreciated. In these talks I’ll discuss the role of moduli in mirror symmetry of Fano varieties (where the mirror is a Landau-Ginzburg (LG) model). Some topics I expect to cover are a general structure theory of moduli of LG models (follows Katzarkov, Kontsevich, Pantev), the interplay of the topology of LG models with autoequivalence relations in the Calabi-Yau setting, and the relationship between Mori theory in the B-model and degenerations of the LG A-model. For the latter topic we’ll focus on the case of del Pezzo surfaces (due to unpublished work of Pantev) and the toric case (due to the speaker with Katzarkov and G. Kerr). Time permitting, we may make some speculations on the role of LG moduli in the work of Gross-Hacking-Keel (in progress work of the speaker with T. Foster).

March 6 and 8
4-5pm
Adam Jacob
(UC Davis)
Title: The deformed Hermitian-Yang-Mills equation
Abstract: In this series I will discuss the deformed Hermitian-Yang-Mills equation, which is a complex analogue of the special Lagrangian graph equation of Harvey-Lawson. I will describe its derivation in relation to the semi-flat setup of SYZ mirror symmetry, followed by some basic properties of solutions. Later I will discuss methods for constructing solutions, and relate the solvability to certain geometric obstructions. Both talks will be widely accessible, and cover joint work with T.C. Collins and S.-T. Yau.

March 6, 8, 13, 15
3-4pm
Dmytro Shklyarov
(TU Chemnitz)
Title: On categories of matrix factorizations and their homological invariants
Abstract: The talks will cover the following topics:
1. Matrix factorizations as D-branes. According to physicists, the matrix factorizations of an isolated hypersurface singularity describe D-branes in the Landau-Ginzburg (LG) B-model associated with the singularity. The talk is devoted to some mathematical implications of this observation. I will start with a review of open-closed topological field theories underlying the LG B-models and then talk about their refinements.
2. Semi-infinite Hodge theory of dg categories. Homological mirror symmetry asserts that the “classical” mirror correspondence relating the number of rational curves in a CY threefold to period integrals of its mirror should follow from the equivalence of the derived Fukaya category of the first manifold and the derived category of coherent sheaves on the second one. The classical mirror correspondence can be upgraded to an isomorphism of certain Hodge-like data attached to both manifolds, and a natural first step towards proving the assertion would be to try to attach similar Hodge-like data to abstract derived categories. I will talk about some recent results in this direction and illustrate the approach in the context of the LG B-models.
3. Hochschild cohomology of LG orbifolds. The scope of applications of the LG mod- els in mirror symmetry is significantly expanded once we include one extra piece of data, namely, finite symmetry groups of singularities. The resulting models are called orbifold LG models or LG orbifolds. LG orbifolds with abelian symmetry groups appear in mir- ror symmetry as mirror partners of varieties of general type, open varieties, or other LG orbifolds. Associated with singularities with symmetries there are equivariant versions of the matrix factorization categories which, just as their non-equivariant cousins, describe D-branes in the corresponding orbifold LG B-models. The Hochschild cohomology of these categories should then be isomorphic to the closed string algebra of the models. I will talk about an explicit description of the Hochschild cohomology of abelian LG orbifolds.

April 10 & 12
3-4pm
Mauricio Romo
(IAS)
Title: Gauged Linear Sigma Models, Supersymmetric Localization and Applications
Abstract: In this series of lectures I will review various results on connections between gauged linear sigma models (GLSM) and mathematics. I will start with a brief introduction on the basic concepts about GLSMs, and their connections to quantum geometry of Calabi-Yaus (CY). In the first lecture I will focus on nonperturbative results on GLSMs on closed 2-manifolds, which provide a way to extract enumerative invariants and the elliptic genus of some classes of CYs. In the second lecture I will move to nonperturbative results in the case where the worldsheet is a disk, in this case nonperturbative results provide interesting connections with derived categories and stability conditions. We will review those and provide applications to derived functors and local systems associated with CYs. If time allows we will also review some applications to non-CY cases (in physics terms, anomalous GLSMs).
Lecture notes

April 17, 19, 26
3-5pm
Andrew Harder
(University of Miami)
Title: Perverse sheaves of categories on surfaces
Abstract: Perverse sheaves of categories on a Riemann surface S are systems of categories and functors which are encoded by a graphs on S, and which satisfy conditions that resemble the classical characterization of perverse sheaves on a disc.
I’ll review the basic ideas behind Kapranov and Schechtman’s notion of a perverse schober and generalize this to perverse sheaves of categories on a punctured Riemann surface. Then I will give several examples of perverse sheaves of categories in both algebraic geometry, symplectic geometry, and category theory. Finally, I will describe how one should be able to use related ideas to prove homological mirror symmetry for certain noncommutative deformations of projective 3-space.

May 15, 17
1-3pm
Charles Doran
(University of Alberta)

Lecture One:
Title: Picard-Fuchs uniformization and Calabi-Yau geometry
Abstract:

Part 1: We introduce the notion of the Picard-Fuchs equations annihilating periods in families of varieties, with emphasis on Calabi-Yau manifolds. Specializing to the case of K3 surfaces, we explore general results on “Picard-Fuchs uniformization” of the moduli spaces of lattice-polarized K3 surfaces and the interplay with various algebro-geometric normal forms for these surfaces. As an application, we obtain a universal differential-algebraic characterization of Picard rank jump loci in these moduli spaces.

Part 2: We next consider families with one natural complex structure modulus, (e.g., elliptic curves, rank 19 K3 surfaces, b_1=4 Calabi-Yau threefolds, …), where the Picard-Fuchs equations are ODEs. What do the Picard-Fuchs ODEs for such families tell us about the geometry of their total spaces? Using Hodge theory and parabolic cohomology, we relate the monodromy of the Picard-Fuchs ODE to the Hodge numbers of the total space. In particular, we produce criteria for when the total space of a family of rank 19 polarized K3 surfaces can be Calabi-Yau.

Lecture Two:
Title: Calabi-Yau fibrations: construction and classification
Abstract:
Part 1: Codimension one Calabi-Yau submanifolds induce fibrations, with the periods of the total space relating to those of the fibers and the structure of the fibration. We describe a method of iteratively constructing Calabi-Yau manifolds in tandem with their Picard-Fuchs equations. Applications include the tower of mirrors to degree n+1 hypersurfaces in P^n and a tower of Calabi-Yau hypersurfaces encoding the n-sunset Feynman integrals.
Part 2: We develop the necessary theory to both construct and classify threefolds fibered by lattice polarized K3 surfaces. The resulting theory is a complete generalization to threefolds of that of Kodaira for elliptic surfaces. When the total space of the fibration is a Calabi-Yau threefold, we conjecture a unification of CY/CY mirror symmetry and LG/Fano mirror symmetry by mirroring fibrations as Tyurin degenerations. The detailed classification of Calabi-Yau threefolds with certain rank 19 polarized fibrations provides strong evidence for this conjecture by matching geometric characteristics of the fibrations with features of smooth Fano threefolds of Picard rank 1.

2020-2021 Colloquium, Wednesdays
2018-01-13 15:25 | MA
During the Spring 2021 semester, and until further notice, all seminars will take place virtually.
The 2020-2021 Colloquium will take place every Wednesday from 9:00 to 10:00am ET virtually, using zoom. All CMSA postdocs/members are required to attend the weekly CMSA Members’ Seminars, as well as the weekly CMSA Colloquium series. Please email the seminar organizers to obtain a link. This year’s colloquium will be organized by Wei Gu and Sergiy Verstyuk. The schedule below will be updated as speakers are confirmed.
To learn how to attend, please fill out this form.
Information on previous colloquia can be found here.

Spring 2021:

Date
Speaker
Title/Abstract

1/27/2021
Evelyn Tang (Max Planck Institute for Dynamics and Self-Organization)
Slides

Video
Title: Topology protects chiral edge currents in stochastic systems
Abstract: Living systems can exhibit time-scales much longer than those of the underlying components, as well as collective dynamical behavior. How such global behavior is subserved by stochastic constituents remains unclear. I will present two-dimensional stochastic networks that consist of out-of-equilibrium cycles at the molecular scale and support chiral edge currents in configuration space. I will discuss the topological properties of these networks and their uniquely non-Hermitian features such as exceptional points and vorticity. As these emergent edge currents are associated to macroscopic timescales and length scales, simply tuning a small number of parameters enables varied dynamical phenomena including a global clock, stochastic growth and shrinkage, and synchronization.

2/3/2021
André Luiz de Gouvêa (Northwestern)
Video
Title: The Brave Nu World
Abstract: Neutrinos are the least understood of the fundamental particles that make up the so-called Standard Model of Particle Physics. Measuring neutrino properties and identifying how they inform our understanding of nature at the smallest distant scales is among the highest priorities of particle physics research today. I will discuss our current understanding of neutrinos, concentrating on the observation of neutrino oscillations and neutrino masses, along with all the open questions that came of these discoveries from the end of the 20th century.

2/10/2021
Mykhaylo Shkolnikov (Princeton)
Video
Title: Probabilistic approach to free boundary problems and applications
Abstract: We will discuss a recently developed probabilistic approach to (singular) free boundary problems, such as the supercooled Stefan problem. The approach is based on a new notion of solution, referred to as probabilistic, which arises naturally in the context of large system limits of interacting particle systems. In the talk, I will give an example of how such interacting particle systems arise in applications (e.g., finance), then obtain a solution of a free boundary problem in the large system limit, and discuss how this solution can be analyzed mathematically (thereby answering natural questions about the systemic risk in financial systems and neural synchronization in the brain). The talk is based on recent and ongoing joint works with Sergey Nadtochiy, Francois Delarue, Jiacheng Zhang and Xiling Zhang

2/17/2021
9:00 – 10:00PM ET
C. Seshadhri (UC Santa Cruz)
Video
Title: Studying the (in)effectiveness of low dimensional graph embeddings
Abstract: Low dimensional graph embeddings are a fundamental and popular tool used for machine learning on graphs. Given a graph, the basic idea is to produce a low-dimensional vector for each vertex, such that “similarity” in geometric space corresponds to “proximity” in the graph. These vectors can then be used as features in a plethora of machine learning tasks, such as link prediction, community labeling, recommendations, etc. Despite many results emerging in this area over the past few years, there is less study on the core premise of these embeddings. Can such low-dimensional embeddings effectively capture the structure of real-world (such as social) networks? Contrary to common wisdom, we mathematically prove and empirically demonstrate that popular low-dimensional graph embeddings do not capture salient properties of real-world networks. We mathematically prove that common low-dimensional embeddings cannot generate graphs with both low average degree and large clustering coefficients, which have been widely established to be empirically true for real-world networks. Empirically, we observe that the embeddings generated by popular methods fail to recreate the triangle structure of real-world networks, and do not perform well on certain community labeling tasks. (Joint work with Ashish Goel, Caleb Levy, Aneesh Sharma, and Andrew Stolman.)

2/24/2021
David Ben-Zvi (U Texas)
Video
Title: Electric-Magnetic Duality for Periods and L-functions
Abstract: I will describe joint work with Yiannis Sakellaridis and Akshay Venkatesh, in which ideas originating in quantum field theory are applied to a problem in number theory.
A fundamental aspect of the Langlands correspondence — the relative Langlands program — studies the representation of L-functions of Galois representations as integrals of automorphic forms. However, the data that naturally index the period integrals (spherical varieties for G) and the L-functions (representations of the dual group G^) don’t seem to line up.
We present an approach to this problem via the Kapustin-Witten interpretation of the [geometric] Langlands correspondence as electric-magnetic duality for 4-dimensional supersymmetric Yang-Mills theory. Namely, we rewrite the relative Langlands program as duality in the presence of supersymmetric boundary conditions. As a result the partial correspondence between periods and L-functions is embedded in a natural duality between Hamiltonian actions of the dual groups.

3/3/2021
9:00pm ET
Omer Tamuz (Caltech)
Title: Monotone Additive Statistics
Abstract: How should a random quantity be summarized by a single number? We study mappings from random variables to real numbers, focussing on those with the following two properties: (1) monotonicity with respect to first-order stochastic dominance, and (2) additivity for sums of independent random variables. This problem turns out to be connected to the following question: Under what conditions on the random variables X and Y does there exist an independent Z so that X + Z first-order stochastically dominates Y + Z?
(Joint work with Tobias Fritz, Xiaosheng Mu, Luciano Pomatto and Philipp Strack.)

3/10/2021
9:00pm ET
Piotr Indyk (MIT)
Title: Learning-Based Sampling and Streaming
Abstract: Classical algorithms typically provide “one size fits all” performance, and do not leverage properties or patterns in their inputs. A recent line of work aims to address this issue by developing algorithms that use machine learning predictions to improve their performance. In this talk I will present two examples of this type, in the context of streaming and sampling algorithms. In particular, I will show how to use machine learning predictions to improve the performance of (a) low-memory streaming algorithms for frequency estimation (ICLR’19), and (b) sampling algorithms for estimating the support size of a distribution (ICLR’21). Both algorithms use an ML-based predictor that, given a data item, estimates the number of times the item occurs in the input data set. (The talk will cover material from papers co-authored with T Eden, CY Hsu, D Katabi, S Narayanan, R Rubinfeld, S Silwal, T Wagner and A Vakilian.

3/17/2021
9:00pm ET
Chiu-Chu Melissa Liu (Columbia)
Title: Topological Recursion and Crepant Transformation Conjecture
Abstract: The Crepant Transformation Conjecture (CTC), first proposed by Yongbin Ruan and later refined/generalized by others, relates Gromov-Witten (GW) invariants of K-equivalent smooth varieties or smooth Deligne-Mumford stacks. We will outline a proof of all-genus open and closed CTC for symplectic toric Calabi-Yau 3-orbifolds based on joint work with Bohan Fang, Song Yu, and Zhengyu Zong. Our proof relies on the Remodeling Conjecture (proposed by Bouchard-Klemm-Marino-Pasquetti and proved in full generality by Fang, Zong and the speaker) relating open and closed GW invariants of a symplectic toric Calabi-Yau 3-orbifold to invariants of its mirror curve defined by Chekhov-Eynard-Orantin Topological Recursion.

3/24/2021
Weinan E (Princeton)
Video
Title: Machine Learning and PDEs
Abstract: I will discuss two topics:
(1) Machine learning-based algorithms and “regularity” theory for very high dimensional PDEs;
(2) Formulating machine learning as PDE (more precisely, integral-differental equation) problems.

3/31/2021
Thore Graepel (DeepMind/UCL)
Video
Title: From AlphaGo to MuZero – Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model
Abstract: Constructing agents with planning capabilities has long been one of the main challenges in the pursuit of artificial intelligence. Tree-based planning methods have enjoyed huge success in challenging domains, such as chess and Go, where a perfect simulator is available. However, in real-world problems the dynamics governing the environment are often complex and unknown. In this work we present the MuZero algorithm which, by combining a tree-based search with a learned model, achieves superhuman performance in a range of challenging and visually complex domains, without any knowledge of their underlying dynamics. MuZero learns a model that, when applied iteratively, predicts the quantities most directly relevant to planning: the reward, the action-selection policy, and the value function. When evaluated on 57 different Atari games – the canonical video game environment for testing AI techniques, in which model-based planning approaches have historically struggled – our new algorithm achieved a new state of the art. When evaluated on Go, chess and shogi, without any knowledge of the game rules, MuZero matched the superhuman performance of the AlphaZero algorithm that was supplied with the game rules.

4/7/2021
Kui Ren (Columbia)
Title: Inversion via Optimization: Revisiting the Classical Least-Squares Formulation of Inverse Problems
Abstract: The classical least-squares formulation of inverse problems has provided a successful framework for the computational solutions of those problems. In recent years, modifications and alternatives have been proposed to overcome some of the disadvantages of this classical formulation in dealing with new applications. This talk intends to provide an (likely biased) overview of the recent development in constructing new least-squares formulations for model and data-driven solutions of inverse problems.

4/14/2021
Siu-Cheong Lau (Boston U)
Title: An algebro-geometric formulation of computing machines
Abstract: Neural network in machine learning has obvious similarity with quiver representation theory. The main gap between the two subjects is that network functions produced from two isomorphic quiver representations are not equal, due to the presence of non-linear activation functions which are not equivariant under the automorphism group. This violates the important math/physics principle that isomorphic objects should produce the same results. In this talk, I will introduce a general formulation using moduli spaces of framed modules of (noncommutative) algebra and fix this gap. Metrics over the moduli space are crucial. I will also explain uniformization between spherical, Euclidean and hyperbolic moduli.

4/21/2021
Vasco Carvalho (Cambridge)
Title: The Economy as a Complex Production Network
Abstract: A modern economy is an intricately linked web of specialized production units, each relying on the flow of inputs from their suppliers to produce their own output, which in turn is routed towards other downstream units. From this production network vantage point we: (i) present the theoretical foundations for the role of such input linkages as a shock propagation channel and as a mechanism for transforming micro-level shocks into macroeconomic, economy-wide fluctuations (ii) selectively survey both empirical and simulation-based studies that attempt to ascertain the relevance and quantitative bite of this argument and (time permitting) (iii) discuss a range of domains where this networked production view is currently being extended to.

4/28/2021
9:00 – 10:00pm ET
Shamit Kachru (Stanford)
Slides
Title: K3 Metrics from String Theory
Abstract: Calabi-Yau manifolds have played a central role in important developments in string theory and mathematical physics. Famously, they admit Ricci flat metrics — but the proof of that fact is not constructive, and the metrics remain mysterious. K3 is perhaps the simplest non-trivial compact Calabi-Yau space. In this talk, I describe two different methods of constructing (smooth, Ricci flat) K3 metrics, and a string theory duality which relates them. The duality re-sums infinite towers of disc instanton corrections via a purely classical infinite-dimensional hyperkahler quotient construction, which can be practically implemented.

Fall 2020:

Date
Speaker
Title/Abstract

9/23/2020
David Kazhdan (Hebrew University)
Title: On Applications of Algebraic Combinatorics to Algebraic Geometry
Abstract: I present a derivation of a number of results on morphisms of a high Schmidt’s rank from a result in Algebraic Combinatorics. In particular will explain the flatness of such morphisms and show their fibers have rational singularities.

10/7/2020
10:00am
Mariangela Lisanti (Princeton University)
Video
Title: Mapping the Milky Way’s Dark Matter Halo with Gaia
Abstract: The Gaia mission is in the process of mapping nearly 1% of the Milky Way’s stars—-nearly a billion in total. This data set is unprecedented and provides a unique view into the formation history of our Galaxy and its associated dark matter halo. I will review results based on the most recent Gaia data release, demonstrating how the evolution of the Galaxy can be deciphered from the stellar remnants of massive satellite galaxies that merged with the Milky Way early on. This analysis is an inherently “big data” problem, and I will discuss how we are leveraging machine learning techniques to advance our understanding of the Galaxy’s evolution. Our results indicate that the local dark matter is not in equilibrium, as typically assumed, and instead exhibits distinctive dynamics tied to the disruption of satellite galaxies. The updated dark matter map built from the Gaia data has ramifications for direct detection experiments, which search for the interactions of these particles in terrestrial targets.

10/14/2020
Gil Kalai (Hebrew University and IDC Herzliya)
Video
Title: Statistical, mathematical, and computational aspects of noisy intermediate-scale quantum computers
Abstract: Noisy intermediate-scale quantum (NISQ) Computers hold the key for important theoretical and experimental questions regarding quantum computers. In the lecture I will describe some questions about mathematics, statistics and computational complexity which arose in my study of NISQ systems and are related to
a) My general argument “against” quantum computers,
b) My analysis (with Yosi Rinott and Tomer Shoham) of the Google 2019 “quantum supremacy” experiment.
Relevant papers:
Yosef Rinott, Tomer Shoham and Gil Kalai, Statistical aspects of the quantum supremacy demonstration, https://gilkalai.files.
wordpress.com/2019/11/stat-quantum2.pdf
Gil Kalai, The Argument against Quantum Computers, the Quantum Laws of Nature, and Google’s Supremacy Claims, https://gilkalai.files.
wordpress.com/2020/08/laws-blog2.pdf
Gil Kalai, Three puzzles on mathematics, computations, and games, https://gilkalai.files.
wordpress.com/2019/09/main-pr.pdf

10/21/2020
Marta Lewicka (University of Pittsburgh)
Video
Title: Quantitative immersability of Riemann metrics and the infinite hierarchy of prestrained shell models
Abstract: We propose results that relate the following two contexts:
(i) Given a Riemann metric G on a thin plate, we study the question of what is its closest isometric immersion, with respect to the distance measured by energies E^h which are modifications of the classical nonlinear three-dimensional elasticity.
(ii) We perform the full scaling analysis of E^h, in the context of dimension reduction as the plate’s thickness h goes to 0, and derive the Gamma-limits of h^{-2n}E^h for all n. We show the energy quantization, in the sense that the even powers 2n of h are the only possible ones (all of them are also attained).
For each n, we identify conditions for the validity of the corresponding scaling, in terms of the vanishing of Riemann curvatures of G up to appropriate orders, and in terms of the matched isometry expansions. Problems that we discuss arise from the description of elastic materials displaying heterogeneous incompatibilities of strains that may be associated with growth, swelling, shrinkage, plasticity, etc. Our results display the interaction of calculus of variations,
geometry and mechanics of materials in the prediction of patterns and shape formation.

10/28/2020
Jonathan Heckman (University of Pennsylvania)
Video
Title: Top Down Approach to Quantum Fields
Abstract: Quantum Field theory (QFT) is the common language of particle physicists, cosmologists, and condensed matter physicists. Even so, many fundamental aspects of QFT remain poorly understood. I discuss some of the recent progress made in understanding QFT using the geometry of extra dimensions predicted by string theory, highlighting in particular the special role of seemingly “exotic” higher-dimensional supersymmetric QFTs with no length scales known as six-dimensional superconformal field theories (6D SCFTs). We have recently classified all examples of such 6D SCFTs, and are now using this to extra observables from strongly correlated systems in theories with more than four spacetime dimensions, as well as in spacetimes with four or fewer spacetime dimensions. Along the way, I will also highlight the remarkable interplay between physical and mathematical structures in the study of such systems

11/4/2020
9:00pm ET
Surya Ganguli (Stanford)
Video
Title: Weaving together machine learning, theoretical physics, and neuroscience through mathematics
Abstract: An exciting area of intellectual activity in this century may well revolve around a synthesis of machine learning, theoretical physics, and neuroscience. The unification of these fields will likely enable us to exploit the power of complex systems analysis, developed in theoretical physics and applied mathematics, to elucidate the design principles governing neural systems, both biological and artificial, and deploy these principles to develop better algorithms in machine learning. We will give several vignettes in this direction, including: (1) determining the best optimization problem to solve in order to perform regression in high dimensions; (2) finding exact solutions to the dynamics of generalization error in deep linear networks; (3) developing interpretable machine learning to derive and understand state of the art models of the retina; (4) analyzing and explaining the origins of hexagonal firing patterns in recurrent neural networks trained to path-integrate; (5) delineating fundamental theoretical limits on the energy, speed and accuracy with which non-equilibrium sensors can detect signals
Selected References:
M. Advani and S. Ganguli, Statistical mechanics of optimal convex inference in high dimensions, Physical Review X, 6, 031034, 2016.
M. Advani and S. Ganguli, An equivalence between high dimensional Bayes optimal inference and M-estimation, NeurIPS, 2016.
A.K. Lampinen and S. Ganguli, An analytic theory of generalization dynamics and transfer learning in deep linear networks, International Conference on Learning Representations (ICLR), 2019.
H. Tanaka, A. Nayebi, N. Maheswaranathan, L.M. McIntosh, S. Baccus, S. Ganguli, From deep learning to mechanistic understanding in neuroscience: the structure of retinal prediction, NeurIPS 2019.
S. Deny, J. Lindsey, S. Ganguli, S. Ocko, The emergence of multiple retinal cell types through efficient coding of natural movies, Neural Information Processing Systems (NeurIPS) 2018.
B. Sorscher, G. Mel, S. Ganguli, S. Ocko, A unified theory for the origin of grid cells through the lens of pattern formation, NeurIPS 2019.
Y. Bahri, J. Kadmon, J. Pennington, S. Schoenholz, J. Sohl-Dickstein, and S. Ganguli, Statistical mechanics of deep learning, Annual Reviews of Condensed Matter Physics, 2020.
S.E. Harvey, S. Lahiri, and S. Ganguli, A universal energy accuracy tradeoff in nonequilibrium cellular sensing, https://arxiv.org/abs/2002.10567

11/11/2020
Kevin Buzzard (Imperial College London)
Video
Title: Teaching proofs to computers
Abstract: A mathematical proof is a sequence of logical statements in a precise language, obeying some well-defined rules. In that sense it is very much like a computer program. Various computer tools have appeared over the last 50 years which take advantage of this analogy by turning the mathematical puzzle of constructing a proof of a theorem into a computer game. The newest tools are now capable of understanding some parts of modern research mathematics. In spite of this, these tools are not used in mathematics departments, perhaps because they are not yet capable of telling mathematicians *something new*.
I will give an overview of the Lean theorem prover, showing what it can currently do. I will also talk about one of our goals: using Lean to make practical tools which will be helpful for future researchers in pure mathematics.

11/18/2020
Jose A. Scheinkman (Columbia)
Video
Title: Re-pricing avalanches
Abstract: Monthly aggregate price changes exhibit chronic fluctuations but the aggregate shocks that drive these fluctuations are often elusive. Macroeconomic models often add stochastic macro-level shocks such as technology shocks or monetary policy shocks to produce these aggregate fluctuations. In this paper, we show that a state-dependent pricing model with a large but finite number of firms is capable of generating large fluctuations in the number of firms that adjust prices in response to an idiosyncratic shock to a firm’s cost of price adjustment. These fluctuations, in turn, cause fluctuations in aggregate price changes even in the absence of aggregate shocks. (Joint work with Makoto Nirei.)

11/25/2020
10:45am
Eric J. Heller (Harvard)
Video
Title: Branched Flow
Abstract: In classical and quantum phase space flow, there exists a regime of great physical relevance that is belatedly but rapidly generating a new field. In evolution under smooth, random, weakly deflecting but persistent perturbations, a remarkable regime develops, called branched flow. Lying between the first cusp catastrophes at the outset, leading to fully chaotic statistical flow much later, lies the visually beautiful regime of branched flow. It applies to tsunami wave propagation, freak wave formation, light propagation, cosmic microwaves arriving from pulsars, electron flow in metals and devices, sound propagation in the atmosphere and oceans, the large scale structure of the universe, and much more. The mathematical structure of this flow is only partially understood, involving exponential instability coexisting with “accidental” stability. The flow is qualitatively universal, but this has not been quantified. Many questions arise, including the scale(s) of the random medium, and the time evolution of manifolds and “fuzzy” manifolds in phase space. The classical-quantum (ray-wave) correspondence in this flow is only partially understood. This talk will be an introduction to the phenomenon, both visual and mathematical, emphasizing unanswered questions

12/2/2020
Douglas Arnold (U of Minnesota)
Video
Title: Preserving geometry in numerical discretization
Abstract: An important design principle for numerical methods for differential equations is that the discretizations preserve key geometric, topological, and algebraic structures of the original differential system. For ordinary differential equations, such geometric integrators were developed at the end of the last century, enabling stunning computations in celestial mechanics and other applications that would have been impossible without them. Since then, structure-preserving discretizations have been developed for partial differential equations. One of the prime examples has been the finite element exterior calculus or FEEC, in which the structures to preserve are related to Hilbert complexes underlying the PDEs, the de Rham complex being a canonical example. FEEC has led to highly successful new numerical methods for problems in fluid mechanics, electromagnetism, and other applications which relate to the de Rham complex. More recently, new tools have been developed which extend the applications of FEEC far beyond the de Rham complex, leading to progress in discretizations of problems from solid mechanics, materials science, and general relativity.

12/9/2020
Manuel Blum and Lenore Blum (Carnegie Mellon)
Video
Title: What can Theoretical Computer Science Contribute to the Discussion of Consciousness?
Abstract: The quest to understand consciousness, once the purview of philosophers and theologians, is now actively pursued by scientists of many stripes. We study consciousness from the perspective of theoretical computer science. This is done by formalizing the Global Workspace Theory (GWT) originated by cognitive neuroscientist Bernard Baars and further developed by him, Stanislas Dehaene, and others. We give a precise formal definition of a Conscious Turing Machine (CTM), also called Conscious AI, in the spirit of Alan Turing’s simple yet powerful definition of a computer. We are not looking for a complex model of the brain nor of cognition but for a simple model of (the admittedly complex concept of) consciousness.
After formally defining CTM, we give a formal definition of consciousness in CTM. We then suggest why the CTM has the feeling of consciousness. The reasonableness of the definitions and explanations can be judged by how well they agree with commonly accepted intuitive concepts of human consciousness, the range of related concepts that the model explains easily and naturally, and the extent of the theory’s agreement with scientific evidence

Simons Collaboration Workshop
2018-01-10 09:00 - 2018-01-13 17:00 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
The CMSA will be hosting a four-day Simons Collaboration Workshop on Homological Mirror Symmetry and Hodge Theory on January 10-13, 2018. The workshop will be held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA.

Confirmed Participants:

Mohammed Abouzaid (Columbia University)
Sergueï Barannikov (Paris Diderot University)
Cheol-Hyun Cho (Seoul National University)
Young-Hoon Kiem (Seoul National University)
Thomas Lam (University of Michigan)
Siu-Cheong Lau (Boston University)
Radu Laza (Stony Brook University)
Si Li (Tsinghua University)
Kaoru Ono (Kyoto University)
Tony Pantev (University of Pennsylvania)
Colleen Robles (Duke University)
Yan Soibelman (Kansas State University)
Kazushi Ueda (University of Tokyo)
Chenglong Yu (Harvard University)
Eric Zaslow (Northwestern University)

Simons Collaboration on Homological Mirror Symmetry
2018-01-02 09:00 - 2018-05-18 17:00 | MA
The Simons Collaboration on Homological Mirror Symmetry brings together a group of leading mathematicians working towards the goal of proving Homological Mirror Symmetry (HMS) in full generality, and fully exploring its applications. This program is funded by the Simons Foundation.
Mirror symmetry, which emerged in the late 1980s as an unexpected physical duality between quantum field theories, has been a major source of progress in mathematics. At the 1994 ICM, Kontsevich reinterpreted mirror symmetry as a deep categorical duality: the HMS conjecture states that the derived category of coherent sheaves of a smooth projective variety is equivalent to the Fukaya category of a mirror symplectic manifold (or Landau-Ginzburg model).
We envision that our goal of proving HMS in full generality can be accomplished by combining three main viewpoints:

categorical algebraic geometry and non-commutative (nc) spaces: in this language, homological mirror symmetry is the statement that the same nc-spaces can arise either from algebraic geometry or from symplectic geometry.
the Strominger-Yau-Zaslow (SYZ) approach, which provides a global geometric prescription for the construction of mirror pairs.
Lagrangian Floer theory and family Floer cohomology, which provide a concrete path from symplectic geometry near a given Lagrangian submanifold to an open domain in a mirror analytic space.

The Center of Mathematical Sciences and Applications is hosting the following short-term visitors for an HMS focused semester:

Jacob Bourjaily (Neils Bohr Institute) 4/1/2018 – 4/14/2018
Colin Diemer (IHES) 2/25/2018 – 3/10/2018
Charles Doran (University of Alberta) 5/13/2018 – 5/25/2018
Baohua Fu (Chinese Academy of Sciences) 4/15/2018 – 4/28/2018
Andrew Harder (University of Miami) 4/15/2018 – 4/28/2018
Shinobu Hosono (Gakushuin University) 2/25/2018 – 3/10/2018
Adam Jacob (UC Davis) 3/5/2018 – 3/16/2018
Tsung-Ju Lee (National Taiwan University) 4/18/2018 – 5/13/2018
Ivan Loseu (Northeastern University) 1/21/2018 – 2/3/2018
Cheuk-Yu Mak (Cambridge University) 4/1/2018 – 4/15/2018
Daniel Pomerleano (Imperial College) 3/19/2018 – 3/23/2018
Mauricio Romo (Tsinghua University) 4/1/2018 – 4/18/ 2018
Emanuel Scheidegger (Albert Ludwigs University of Freiburg) 2/22/2018 – 3/22/2018
Dmytro Shklyarov (Technische Universität Chemnitz) 3/4/2018 – 3/17/2018
Alan Thompson (University of Cambridge) 4/15/2018 – 4/21/2018
Weiwei Wu (University of Georgia) 4/27/2018 – 5/6/2018
Matt Young (Chinese University of Hong Kong) 1/15/2018 – 2/9/2018
Jeng-Daw Yu (National Taiwan University) 4/2/2018 – 4/6/2018
Minxian Zhu (Yau Mathematical Sciences Center, Tsinghua University) 1/ 22/2018 – 2/25/2018

As part of their CMSA visitation, HMS focused visitors will be giving lectures on various topics related to Homological Mirror Symmetry throughout the Spring 2018 Semester. Click here for information.

The Collaboration will include two workshops hosted by The Center. The workshops will take place January 10-13, 2018 and April 5-7, 2018 at CMSA. Click here for more information.

11-15-17 RM & PT Seminar
2017-12-15 13:55 | MA

12-6-2017 Mathematical Physics Seminar
2017-12-06 14:17 | MA

12-6-2017 RM & PT Seminar
2017-12-06 14:16 | MA

11-29-2017 Mathematical Physics Seminar
2017-11-29 14:11 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States

11-29-17 RM & PT Seminar
2017-11-29 14:03 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States

11-20-2017 RM & PT Seminar
2017-11-20 14:00 | MA

11-13-2017 Mathematical Physics Seminar
2017-11-13 13:53 | MA

Workshop on Algebraic Methods in Combinatorics
2017-11-13 09:00 - 2017-11-17 16:00 | CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
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

11-10-2017 RM & PT Seminar
2017-11-10 13:48 | MA

Jennifer Chayes Public Talk
2017-11-02 17:00 - 18:00 | Askwith Hall, Harvard University
Jennifer Chayes (Microsoft Research) will be giving a public talk on November 02, 2017, as part of the Program on combinatorics and complexity hosted by the CMSA during AY17-18. The talk will be at 5:00pm in Askwith Hall, 13 Appian Way, Cambridge, MA.
Title: Network Science: From the Online World to Cancer Genomics
Abstract: Everywhere we turn these days, we find that networks can be used to describe relevant interactions. In the high tech world, we see the Internet, the World Wide Web, mobile phone networks, and a variety of online social networks. In economics, we are increasingly experiencing both the positive and negative effects of a global networked economy. In epidemiology, we find disease spreading over our ever growing social networks, complicated by mutation of the disease agents. In biomedical research, we are beginning to understand the structure of gene regulatory networks, with the prospect of using this understanding to manage many human diseases. In this talk, I look quite generally at some of the models we are using to describe these networks, processes we are studying on the networks, algorithms we have devised for the networks, and finally, methods we are developing to indirectly infer network structure from measured data. I’ll discuss in some detail particular applications to cancer genomics, applying network algorithms to suggest possible drug targets for certain kinds of cancer.

10-25-17 RMPT Seminars
2017-10-25 13:45 | MA

10-23-17 Mathematical Physics Seminar
2017-10-23 13:43 | MA

2017 Ding Shum Lecture
2017-10-10 17:00 - 18:00 | Harvard Science Center, 1 Oxford Street, Cambridge, MA, 02138
Leslie Valiant will be giving the inaugural talk of the Ding Shum Lectures on Tuesday, October 10 at 5:00 pm in Science Center Hall D, Cambridge, MA.
Learning as a Theory of Everything
Abstract: We start from the hypothesis that all the information that resides in living organisms was initially acquired either through learning by an individual or through evolution. Then any unified theory of evolution and learning should be able to characterize the capabilities that humans and other living organisms can possess or acquire. Characterizing these capabilities would tell us about the nature of humans, and would also inform us about feasible targets for automation. With this purpose we review some background in the mathematical theory of learning. We go on to explain how Darwinian evolution can be formulated as a form of learning. We observe that our current mathematical understanding of learning is incomplete in certain important directions, and conclude by indicating one direction in which further progress would likely enable broader phenomena of intelligence and cognition to be realized than is possible at present.

The 2017 Charles River Lectures
2017-10-02 09:15 - 17:30 | Harvard Science Center, 1 Oxford Street, Cambridge, MA, 02138
Charles River with Bench at Sunset
Jointly organized by Harvard University, Massachusetts Institute of Technology, and Microsoft Research New England, the Charles River Lectures on Probability and Related Topics is a one-day event for the benefit of the greater Boston area mathematics community.
The 2017 lectures will take place 9:15am – 5:30pm on Monday, October 2 at Harvard University in the Harvard Science Center.

***************************************************
UPDATED LOCATION
Harvard University
Harvard Science Center (Halls C & E)
1 Oxford Street, Cambridge, MA 02138 (Map)
Monday, October 2, 2017
9:15 AM – 5:30 PM
**************************************************
Please note that registration has closed.
Speakers:

Paul Bourgade (Courant Institute, NYU)
Massimiliano Gubinelli (University of Bonn)
Andrea Montanari (Stanford University)
Roman Vershynin (University of California, Irvine)
Ofer Zeitouni (Weizmann Institute)

Agenda:
In Harvard Science Center Hall C:
8:45 am – 9:15 am: Coffee/light breakfast
9:15 am – 10:15 am: Ofer Zeitouni
Title: Noise stability of the spectrum of large matrices
Abstract: The spectrum of large non-normal matrices is notoriously sensitive to perturbations, as the example of nilpotent matrices shows. Remarkably, the spectrum of these matrices perturbed by polynomially (in the dimension) vanishing additive noise is remarkably stable. I will describe some results and the beginning of a theory.
The talk is based on joint work with Anirban Basak and Elliot Paquette, and earlier works with Feldheim, Guionnet, Paquette and Wood.

10:20 am – 11:20 am: Andrea Montanari
Title: Algorithms for estimating low-rank matrices
Abstract: Many interesting problems in statistics can be formulated as follows. The signal of interest is a large low-rank matrix with additional structure, and we are given a single noisy view of this matrix. We would like to estimate the low rank signal by taking into account optimally the signal structure. I will discuss two types of efficient estimation procedures based on message-passing algorithms and semidefinite programming relaxations, with an emphasis on asymptotically exact results.
11:20 am – 11:45 am: Break
11:45 am – 12:45 pm: Paul Bourgade
Title: Random matrices, the Riemann zeta function and trees
Abstract: Fyodorov, Hiary & Keating have conjectured that the maximum of the characteristic polynomial of random unitary matrices behaves like extremes of log-correlated Gaussian fields. This allowed them to predict the typical size of local maxima of the Riemann zeta function along the critical axis. I will first explain the origins of this conjecture, and then outline the proof for the leading order of the maximum, for unitary matrices and the zeta function. This talk is based on joint works with Arguin, Belius, Radziwill and Soundararajan.
1:00 pm – 2:30 pm: Lunch
In Harvard Science Center Hall E:
2:45 pm – 3:45 pm: Roman Vershynin
Title: Deviations of random matrices and applications
Abstract: Uniform laws of large numbers provide theoretical foundations for statistical learning theory. This lecture will focus on quantitative uniform laws of large numbers for random matrices. A range of illustrations will be given in high dimensional geometry and data science.
3:45 pm – 4:15 pm: Break
4:15 pm – 5:15 pm: Massimiliano Gubinelli
Title: Weak universality and Singular SPDEs
Abstract: Mesoscopic fluctuations of microscopic (discrete or continuous) dynamics can be described in terms of nonlinear stochastic partial differential equations which are universal: they depend on very few details of the microscopic model. This universality comes at a price: due to the extreme irregular nature of the random field sample paths, these equations turn out to not be well-posed in any classical analytic sense. I will review recent progress in the mathematical understanding of such singular equations and of their (weak) universality and their relation with the Wilsonian renormalisation group framework of theoretical physics.
Organizers:
Alexei Borodin, Henry Cohn, Vadim Gorin, Elchanan Mossel, Philippe Rigollet, Scott Sheffield, and H.T. Yau

Workshop on Additive Combinatorics, Oct. 2-6, 2017
2017-10-02 09:00 - 2017-10-06 16:00 | CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
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

9-27-17 Mathematical Physics Seminar
2017-09-27 13:42 | MA

9-27-17 RM&PT Seminar
2017-09-27 13:41 | MA

9-18-17 Mathematical Physics Seminar
2017-09-18 13:39 | MA

Algebraic Geometry Seminar, Thursdays
2017-09-14 15:00 - 16:00 | MA
This seminar will not be held in the Spring 2018 Semester.
The Algebraic Geometry Seminar will be every Thursday from 3pm-4pm in CMSA Building, 20 Garden Street, Room G10.
The schedule will be updated as details are confirmed.

Date
Name
Title/Abstract

09-14-17
Yu-Wei Fan (Harvard Math)

Entropy of an autoequivalence on Calami-Yau manifolds
Abstract: We will recall the notion of entropy of an autoequivalence on triangulated categories, and provide counterexamples of a conjecture by Kikuta-Takahashi.

11-1-17
*5:00pm, G10*
Shamil Shakirov, Harvard Math

Undulation invariants of plane curves
Abstract: “One of the general problems in algebraic geometry is to determine algorithmically whether or not a given geometric object, defined by explicit polynomial equations (e.g. a curve or a surface), satisfies a given property (e.g. has singularities or other distinctive features of interest). A classical example of such a problem, described by Cayley and Salmon in 1852, is to determine whether or not a given plane curve of degree r > 3 has undulation points — the points where the tangent line meets the curve with multiplicity four. Cayley proved that there exists an invariant of degree (r – 3)(3 r – 2) that vanishes if and only if the curve has undulation points. We construct this invariant explicitly for quartics (r=4) as the determinant of a 21 times 21 matrix with polynomial entries, and we conjecture a generalization for r = 5

11-2-17

Alexander Moll, IHES

Hilbert Schemes from Geometric Quantization of Dispersive Periodic Benjamin-Ono Waves
ABSTRACT: By Grojnowski and Nakajima, Fock spaces are cohomology rings of Hilbert scheme of points in the plane. On the other hand, by Pressley-Segal, Fock spaces are spaces of J-holomorphic functions on the loop space of the real line that appear in geometric quantization with respect to the Kähler structure determined by the Sobolev regularity s= -1/2 and the Hilbert transform J. First, we show that the classical periodic Benjamin-Ono equation is a Liouville integrable Hamiltonian system with respect to this Kähler structure. Second, we construct an integrable geometric quantization of this system in Fock space following Nazarov-Sklyanin and describe the spectrum explicitly after a non-trivial rewriting of our coefficients of dispersion ebar = e_1 + e_2 and quantization hbar = – e_1 e_2 that is invariant under e_2 <-> e_1. As a corollary of Lehn’s theorem, our construction gives explicit creation and annihilation operator formulas for multiplication by new explicit universal polynomials in the Chern classes of the tautological bundle in the equivariant cohomology of our Hilbert schemes, in particular identifying ebar with the deformation parameter of the Maulik-Okounkov Yangian and hbar with the handle-gluing element. Our key ingredient is a simple formula for the Lax operators as elliptic generalized Toeplitz operators on the circle together with the spectral theory of Boutet de Monvel and Guillemin. As time permits, we discuss the relation of dispersionless ebar -> 0 and semi-classical hbar rightarrow 0 limits to Nekrasov’s BPS/CFT Correspondence.

11-9-17
TBD
TBD

11-16-17
TBD
TBD

11-23-17
TBD
TBD

11-30-17
TBD
TBD

12-7-17
TBD
TBD

12-15-17
TBD
TBD

9/11/2017 Mathematical Physics Seminar
2017-09-11 13:38 | MA
