International Congress of Mathematicians 2022 July 6–14 Proceedings: Sections 12-14

Front cover
Front matter
Contents
12. Probability – Special lecture
E. Mossel: Combinatorial statistics and the sciences
1. Introduction
1.1. A simple model on trees
1.2. Belief propagation and the reconstruction problem
2. Linear theory and the Kesten–Stigum bound
3. Nonlinear theory
4. Connections to statistical physics
4.1. Detection in the block model
4.2. q=2—linear theory
4.3. Nonlinear theory
5. Connections to molecular biology
6. Connections to theoretical computer science
6.1. Recursive bounded memory algorithms
6.2. The complexity of P[X_0 | X_h]
References
12. Probability
J. Baik: TASEP
1. Introduction
2. TASEP, corner growth model, and exponential DLPP
2.1. TASEP
2.2. Corner growth model
2.3. Exponential DLPP
2.4. Hydrodynamic limit and KPZ limit
3. One-point distribution
3.1. Poisson DLPP
3.2. Longest increasing subsequence
3.3. Exponential DLPP
3.4. Integrable models
4. Multipoint distributions
5. Half-infinite space
6. Ring domain
7. Formula of multipoint distribution functions
7.1. Formula for KPZ fixed point
7.2. Formula for the periodic case
7.3. Transition probabilities
8. Integrable differential equations
9. Comments on universality
9.1. Thin DLPP
9.2. Interacting particle systems
9.3. TASEP, Coulomb gas, and random matrices
9.4. Universality in many directions
References
J. Ding, J. Dubédat, and E. Gwynne: Introduction to the Liouville quantum gravity metric
1. Introduction
1.1. Definition of LQG
1.2. Area measure and conformal covariance
1.3. Motivation
2. Construction of the LQG metric
2.1. Liouville first passage percolation
2.2. Convergence in the subcritical case
2.2.1. Tightness
2.2.2. Uniqueness
2.2.3. Weak LQG metrics
2.3. The supercritical and critical cases
2.3.1. Subsequential limits
2.3.2. Central charge
2.4. Alternative construction and planar map connection for γ=\sqrt{8/3}
3. Properties of the LQG metric
3.1. Dimension
3.2. Quantitative estimates
3.3. Geodesics
3.4. Metric balls
3.5. KPZ formula
4. Tools for studying the LQG metric
4.1. Adding a bump function
4.2. Independence across concentric annuli
4.3. White noise decomposition
5. Open problems
References
R. Eldan: Analysis of high-dimensional distributions using pathwise methods
1. Introduction
2. A first taste of pathwise analysis: concentration of Lipschitz functions in Gaussian space
3. The Gaussian isoperimetric inequality and noise-sensitivity
4. Stochastic Localization and the KLS conjecture
4.1. Construction of the process and basic properties
4.2. Isoperimetry for log-concave measures using Stochastic Localization
4.2.1. Stochastic Localization as a moment-generating process
4.2.2. Obtaining a bound for the KLS conjecture
5. Decomposition of measures and further applications of Stochastic Localization
5.1. Needle decompositions
5.1.1. A waist inequality for complex-analytic functions
5.2. Measures on the discrete hypercube
5.2.1. Concentration for Ising models via decomposition into low-rank systems
5.2.2. Entropy-efficient decomposition of discrete measures
References
A. M. Etheridge: Modeling hybrid zones
1. Introduction
2. Hybrid zones and curvature flow
2.1. Modeling selection against heterozygosity
2.2. (Mean) curvature flow
2.3. The motion of hybrid zones
3. A probabilistic representation of solutions to (1.4)
4. Long-range dispersal
5. Asymmetry and blocking
5.1. An asymmetric reaction: homozygotes of different fitnesses
5.2. Geometry matters: blocking
6. Adding noise
6.1. Adding (genic) selection to the SLFV
6.2. The effect of genetic drift on blocking
Weak noise/selection ratio
Strong noise/selection ratio
7. Conclusion
References
T. Funaki: Hydrodynamic limit and stochastic PDEs
1. Introduction
2. Motion by mean curvature
2.1. From particle systems
2.1.1. Glauber–zero-range process and hydrodynamic limit with fixed K
2.1.2. Mesoscopic Glauber perturbation and derivation of MMC
2.1.3. Proof of Theorem 2.1
2.2. Other approaches
2.2.1. Ginzburg–Landau interface model
2.2.2. SPDE approach to stochastic MMC
3. Stefan problem
3.1. From two-component Glauber–Kawasaki dynamics
3.2. From two-component Kawasaki dynamics with speed change and annihilation
3.2.1. One-phase Stefan problem (Immobile Ice)
3.2.2. Two-phase Stefan problem (Mobile Ice)
4. KPZ equation
4.1. KPZ equation as singular SPDE
4.1.1. Scalar KPZ equation
4.1.2. Coupled KPZ equation
4.1.3. Two approximations, local and global well-posedness and invariant measure
4.1.4. Proof of Theorems 4.1 and 4.2
4.2. From interacting particle systems
4.2.1. n-species zero-range process on T_N
4.2.2. Hydrodynamic limit and linear fluctuation
4.2.3. Nonlinear fluctuation leading to coupled KPZ–Burgers equation
4.3. Related results
4.3.1. Stochastic eight-vertex model
4.3.2. Related singular quasilinear SPDE
References
P. Gonçalves: On the universality from interacting particle systems
1. Introduction
2. Exclusion process: a prototype model with one conservation law
2.1. Hydrodynamic limit
2.2. Fluctuations
3. A prototype model with two conservation laws
3.1. Hydrodynamic limits
3.2. Predictions from mode coupling theory
3.3. Choice of the fluctuations fields
3.4. Limiting equations
3.4.1. Case (I)
3.4.2. Case (II)
3.5. The harmonic case
References
H. Lacoin: Mixing time for 1D particle systems
1. A short introduction to Markov chains
1.1. Definition of a Markov chain
1.2. Markov semigroup, generator, invariant measures, and reversibility
1.2.1. Finite state-space case
1.2.2. Continuum state-space case
1.3. Total variation distance and mixing time
1.4. Organization of the paper
2. One-dimensional particle systems and interface models
2.1. The interchange process on a segment
2.2. The exclusion process on the segment
2.3. The corner-flip dynamics
2.4. Random walk on the simplex
2.5. Correspondences
3. Review of mixing-time results for one-dimensional particle systems
3.1. The cutoff phenomenon
3.2. Mixing time results
3.3. Review of related works
4. A few technical tools used to prove these results
4.1. Order preservation
4.2. Connection with the discrete heat equation
4.2.1. The symmetric case
4.2.2. The asymmetric case
4.3. Using the heat equations to obtain bounds on the mixing time
5. Shortcomings and possible improvements of the reasoning above
5.1. Symmetric dynamics
5.2. Asymmetric dynamics
References
D. Panchenko: Ultrametricity in spin glasses
1. Introduction
2. Some background
3. The Ghirlanda–Guerra identities
4. Synchronization mechanism
5. Other applications of ultrametricity
6. Some related work
References
K. Ramanan: Interacting processes on sparse graphs
1. Introduction
1.1. Background
1.2. Questions of interest
2. Classical mean-field results for interacting stochastic processes
2.1. Interacting diffusions
2.2. Mean-field limits and nonlinear diffusion processes
2.3. Interacting jump processes and their mean-field limits
2.3.1. Description of dynamics
2.3.2. Mean-field limits and nonlinear jump processes
2.4. Limitations of mean-field approximations
3. Interacting processes on sparse graphs: hydrodynamic limits
3.1. Local convergence of sparse graph sequences
3.2. Hydrodynamic limits
3.2.1. Interacting diffusion processes
3.2.2. Interacting jump processes
4. Marginal dynamics on trees
4.1. A Markov random field property
4.2. Outline of derivation of the local equation for diffusions on the line
4.3. Local equations for diffusions on unimodular Galton–Watson trees
4.4. Marginal dynamics for pure jump processes
4.5. Generalizations and approximations
5. Open questions
References
D. Remenik: Integrable fluctuations in the KPZ universality class
1. The KPZ universality class
2. TASEP with special initial data
3. General solution of TASEP
4. The KPZ fixed point
5. Integrability of the KPZ fixed point transition probabilities
6. KP in special solutions of the KPZ equation
References
L. Saloff-Coste: Heat kernel estimates
1. Introduction
2. Existence
3. The geometry of nice Dirichlet spaces
4. Harnack manifolds and Dirichlet spaces
5. Non-Harnack manifolds
6. Manifolds made of nice pieces and reconstruction: basic examples
7. Manifolds with finitely many nonparabolic Harnack ends
8. Nonparabolic manifolds with finitely many Harnack ends
9. Parabolic manifolds with finitely many Harnack ends
10. Mixed boundary conditions on Harnack manifolds
11. Mixed boundary conditions on manifolds with ends
12. Attachments along noncompact submanifolds
References
13. Combinatorics – Special lecture
M. M. Wood: Probability theory for random groups arising in number theory
1. Introduction
1.1. Notation and conventions
2. The moment problem
2.1. Robust uniqueness for random abelian groups
2.2. When uniqueness fails
2.3. Random finite abelian groups with additional structure
2.4. Random nonabelian groups
3. Universality
3.1. Random finite abelian groups
3.2. Random finite abelian groups with additional structure
3.3. Random nonabelian groups
References
13. Combinatorics
F. Ardila: The geometry of geometries: matroid theory, old and new
1. Introduction
2. Matroids
3. Enumerative invariants
3.1. Computing Tutte polynomials: the finite field method
4. Geometric model 1: matroid polytopes
4.1. Algebraic geometry
4.2. A geometric characterization of matroids
4.3. Combinatorial optimization and generalized permutahedra
4.4. Matroid subdivisions
4.5. Matroid valuations
4.6. Hopf algebras and valuations
5. Geometric model 2: Bergman fans
5.1. Tropical geometry
5.2. A tropical characterization of matroids
5.3. The Chow ring, combinatorial Hodge theory, and log-concavity
5.4. Chern–Schwartz–MacPherson cycles of matroids
6. Geometric model 3: conormal fans
6.1. The conormal Chow ring and combinatorial Hodge theory
6.2. Lagrangian interpretation of CSM classes
6.3. Unimodality, log-concavity, and flawlessness
6.4. Lagrangian combinatorics, bipermutahedra, and harmonic polytopes
7. Geometry and geometries: the future
References
J. Böttcher: Graph and hypergraph packing
1. Introduction and background
2. Notation and basic definitions
3. Designs
4. Packing cycles
5. Packing trees
6. Packing more general graph classes
7. Packing large hypergraphs
8. Some open problems
References
E. Friedgut: KKL’s influence
1. Introduction
1.1. Basic terminology and definitions
2. Problems
2.1. Juntas rule
2.2. Almost-dictator functions
2.3. Thresholds for every graph property
2.4. Sharp/coarse thresholds – global/local properties
2.5. Maximizing copies of one (hyper)graph in another
2.6. The traffic light problem
2.7. Subsets of independent sets in product graphs
2.8. t-intersecting subsets of the cube
2.9. Triangle-intersecting families of graphs
2.10. Intersecting families of permutations
3. Approaches and techniques
3.1. Juntas rule
3.2. Almost-dictator functions
3.3. Thresholds for every graph property
3.4. Sharp/coarse thresholds – global/local properties
3.5. Maximizing copies of one (hyper)graph in another
3.6. The traffic light problem
3.7. Subsets of independent sets in product graphs
3.8. t-intersecting subsets of the cube
3.9. Triangle-intersecting families of graphs
3.10. Intersecting families of permutations
References
A. Knutson: Schubert calculus and quiver varieties
1. Littlewood–Richardson coefficients
1.1. From intersection theory on Grassmannians
1.2. From representation theory
1.3. From group theory
1.4. Combinatorial approaches
2. Several independent axes of generalization
2.1. K-theory [K]
2.2. T-equivariant cohomology [T]
2.3. Larger flag manifolds [F]
2.4. Quantum cohomology [Q]
2.5. Other Lie groups [G]
2.6. Cotangent Schubert calculus [C]
2.7. Mixing and matching
2.8. A few other generalizations
3. Quiver varieties, stable envelopes, and stable bases
3.1. Quiver varieties
3.2. Stable envelopes and bases
3.3. Comparison of stable bases
4. A factorization of correspondences gives the puzzle rule
4.1. d=2,3,4,≥5
5. Future directions
References
S. Norin: Recent progress towards Hadwiger’s conjecture
1. Introduction
2. Basic dependencies
3. Density
4. Density increment
5. Building the minors
6. Bringing it all together
References
I. Novik: Face numbers
1. Introduction
2. Some basics
3. The cyclic polytope and McMullen's Upper Bound Theorem
4. Spheres, manifolds, and Eulerian complexes
5. Witt spaces
6. The g-conjecture
7. Numbers of neighborly polytopes and neighborly spheres
8. The upper bound theorem for centrally symmetric spheres
9. How neighborly can a cs polytope be?
10. Towards an Upper Bound Conjecture for cs polytopes
References
M. Schacht: Restricted problems in extremal combinatorics
1. Introduction
2. Extremal problems for graphs and hypergraphs
3. Hypergraphs uniformly dense on sets of vertices
4. Hypergraphs uniformly dense on vertices and pairs
5. Hypergraphs uniformly dense on pairs of sets of pairs
References
A. Scott: Graphs of large chromatic number
1. Introduction
2. Girth and chromatic number
3. Perfect graphs
4. χ-bounded classes and the Gyárfás–Sumner conjecture
5. Holes in graphs of large chromatic number
6. Induced subdivisions and geometric constructions
7. The Erdős–Hajnal Conjecture
8. Polynomial bounds and Esperet's conjecture
9. Graph minors and induced subgraphs
References
A. Shapira: Local-vs-global combinatorics
1. Introduction
2. The Brown–Erdős–Sós conjecture
2.1. Approximate versions of BESC
2.2. Lower bounds for BESC
2.3. The Gowers–Long conjecture
2.4. A Ramsey variant of BESC
3. Variants of the regularity lemma and their applications
3.1. Triangle removal using weak regularity lemmas
3.2. Improved bounds for the induced removal lemma?
3.3. The hypergraph regularity lemma
4. Variants of the removal lemma
4.1. A theoretical computer science interlude
4.2. Removal lemmas with polynomial bounds
4.3. Removal lemmas of prescribed growth and generalized Turán problems
4.4. Three generalizations of induced F-freeness
4.5. Arithmetic removal lemmas for linear equations and functions
References
L. K. Williams: The positive Grassmannian, the amplituhedron, and cluster algebras
1. Introduction
2. The positive Grassmannian and matroid stratification
2.1. The Grassmannian and the matroid stratification
2.2. The positive Grassmannian
2.3. The positroid cell decomposition
2.4. φ-induced subdivisions and positroid tilings
3. The moment map and positroid tilings
3.1. Classification of positroid tiles for the moment map
3.2. The positive tropical Grassmannian and positroid subdivisions
3.3. Realizability of positively oriented matroids
4. The amplituhedron and the sign stratification
5. The amplituhedron map and positroid tilings
5.1. Classification of positroid tiles for the amplituhedron map when m=2
5.2. Numerology of positroid tilings of the amplituhedron
6. T-duality and positroid tilings of Δ_{k+1,n} and A_{n,k,2}
7. The amplituhedron and cluster algebras
7.1. Cluster adjacency for facets of positroid tiles
7.2. Positroid tiles as totally positive parts of cluster varieties
8. Future directions
References
14. Mathematics of Computer Science – Special lectures
C. Dwork: Differential privacy: getting more for less
1. Introduction
2. Pure differential privacy
3. Two primitives
4. Relaxations of pure differential privacy
4.1. Approximate differential privacy
4.2. (t)Concentrated and Rényi differential privacy
4.3. Some relationships among the relaxations
5. Privacy amplificaton techniques
5.1. Amplification by subsampling
5.2. Amplification by shuffling
5.3. Amplification by secrecy of the journey
6. Applications
6.1. Privacy via subsampling in gradient descent
6.2. Privacy amplification via shuffling
6.3. Privacy of the journey
6.3.1. Very large numbers of iterations
References
A. Jain, H. Lin, and A. Sahai: Indistinguishability obfuscation
1. Introduction
1.1. Assumptions in more detail
1.2. Applications of iO
1.3. Prior work on the feasibility of iO
1.4. Open problems
2. Technical overview: How to construct iO?
2.1. Preliminaries
2.2. Simplifying the task of iO
2.3. Special encryption for NC^0 mappings
3. Structured seed PRG
3.1. Definition of structured-seed PRG
3.2. Construction of structured-seed PRG
References
D. Silver and A. Barreto: Simulation-based search
1. Introduction
2. Related work
3. Operators
3.1. State and state–action operators
3.2. Sample-based evaluation
4. Search control
4.1. Backup diagrams for search control
4.2. Simulation
4.3. Recursive simulation
5. Approximation
6. Discussion
References
B. Sturmfels: Beyond linear algebra
1. Introduction
2. Nearest points on algebraic varieties
3. Likelihood geometry
4. Nonlinear algebra meets linear PDEs
References
14. Mathematics of Computer Science
R. Gotlib and T. Kaufman: Nowhere to go but high: a perspective on high-dimensional expanders
1. Introduction
2. Some classical facts about expander graphs
2.1. Weighted graphs
2.2. Spectral expansion of graphs
2.3. Topological expansion of graphs
3. High-dimensional expanders: The object of study
3.1. Simplicial complexes and links
3.2. Weighted simplicial complexes and weighted links
3.3. Spectral definition of high-dimensional expansion
3.4. Topological definition of high-dimensional expansion
4. Random walks on high-dimensional expanders
5. Local-to-global spectral expansion of high-dimensional expanders
6. Local-to-global topological expansion of high-dimensional expanders
7. High-dimensional expansion and local testability of codes
8. High-dimensional expansion and quantum LDPC codes
9. Gromov topological overlapping problem via topological high-dimensional expanders
10. Sampling bases of a matroid using local spectral expanders
11. Additional topics that are not covered in this note
References
J. Nelson: Forty years of frequent items
1. The early work
2. Problem reformulations and more general algorithms
2.1. ℓ_2 heavy hitters and the turnstile model
2.2. A digression on pseudorandomness
3. Impossibility results
3.1. ℓ_p heavy hitters for p>2
4. State-of-the-art algorithms
4.1. Insertion-only streams: the BPTree
4.1.1. A brief introduction to chaining arguments
4.2. General turnstile streams: the ExpanderSketch
5. Frequent items with privacy constraints
References
O. Regev: Some questions related to the reverse Minkowski theorem
1. Introduction
2. Reverse Minkowski theorem for the Gaussian mass
3. Reverse Minkowski theorem for the zeta function
4. Proof overview
5. Implications to the geometry of Voronoi cells and convex bodies
6. Covering radius
References
M. Safra: Mathematics of computation through the lens of linear equations and lattices
1. Synopsis
2. History
2.1. Lattices take center stage
2.2. Hardness assumptions
3. Foundation: a system of linear equations
3.1. Error correcting codes (ECC)
3.2. Complexity of approximation
3.3. General norm
3.4. Alternative measures
3.5. Average-case complexity
3.5.1. SIS
3.5.2. Learning-with-Errors
3.6. Discrete subgroup—Lattices
3.7. Worst-to-average-case
4. Plan: In a class of their own
4.1. Break the soundness barrier
4.2. Through lattices
4.3. What's hard with lattices?
4.4. Synergy
5. About computational complexity and PCP
5.1. The dawn of NP-hardness
5.2. The PCP era
5.3. Fourier transform and analysis of Boolean functions
5.4. The UGC revolution
5.5. Present and future
5.6. Related open problems
6. Discussion
A. The Complexity of CVP
A.1. CVP is NP-hard
B. Foundations of lattices
B.1. Elementary, my dear
B.2. Minkowski
B.3. Fourier transform over lattices, etc.
B.4. The Korkin–Zolotarev basis
B.5. The LLL algorithm
B.5.1. The algorithm
B.6. Extension
B.7. CVP algorithm
B.7.1. Babai's nearest plane algorithm
References
O. Svensson: Polyhedral techniques in combinatorial optimization: matchings and tours
1. Introduction
2. The algorithms that must exist for perfect matchings
2.1. Randomized parallel algorithms for the perfect matching problem
2.2. Fenner, Gurjar, and Thierauf's approach for bipartite graphs
2.3. Polyhedral techniques for general graphs
2.4. Future directions
3. The (asymmetric) traveling salesman problem
3.1. Designing approximation algorithms for ATSP
3.2. The repeated cycle cover approach
3.3. The spanning tree approach
3.4. General distances are not that general: a constant factor approximation
3.5. Future directions
References
T. Vidick: MIP* = RE
1. Introduction
2. Problem statement(s)
2.1. Connes' embedding problem
2.2. Tsirelson's problem
3. Separating hyperplanes as nonlocal games
3.1. Nonlocal games
3.2. The game algebra
4. Constructing nonlocal games
4.1. The Magic Square game
4.2. The Pauli braiding game
4.3. A fixed-point argument
4.4. Enter complexity
5. Compression
5.1. The PCP theorem and answer reduction
5.2. Rigidity and question reduction
5.3. The quantum low-degree test
5.4. MIP* = RE
6. Outlook
References
List of contributors
Back cover