The seminar meets on Tuesdays, 14:30-15:30, in Math -101

This Week


Yotam Dikstein (IAS)

High Dimensional Expanders and Chernoff Inequalities

Chernoff’s inequality is one of the most basic inequalities in probability theory. It states that the sum of independent random variables is close to its mean with very high probability. The `Expander-Graph Chernoff inequality’, proven by Ajtai, Komlos, and Szemeredi in 1987, is a powerful extension of Chernoff’s inequality, asserting that Chernoff’s inequality holds even when sampling the random variables using paths in an expander graph instead of sampling them independently.

In this talk, we will discuss further extensions and generalizations of Chernoff’s inequality coming from high dimensional expanders. High dimensional expanders are sparse hypergraphs exhibiting pseudo-random properties. These are more sophisticated structures than the expander graphs of [AKS], but in return the generalization of Chernoff’s bound obtained from them applies in a far more general setup.

We will see why Chernoff-type bounds hold for high dimensional expanders, and how this inequality arises naturally in problems in high dimensional geometry and computational complexity.

This is based on joint work with Max Hopkins. The talk will not assume prior background in complexity theory and is aimed at a broad audience.


2025–26–A meetings

Upcoming Meetings

Date
Title
Speaker
Abstract
Jan 20 TBAOnline Itay Glazer (Technion)

TBA

Past Meetings

Date
Title
Speaker
Abstract
Oct 28 TBA Departmental meeting (BGU)
Nov 4 Orthogonal families of hypergeometric polynomials Dmitry Gourevitch (Weizmann Institute)

We consider quasi-orthogonal polynomial families - those that are orthogonal with respect to a non-degenerate bilinear form defined by a linear functional - in which the ratio of successive coefficients is given by a rational function f(n,k) which is polynomial in n. Here, n is the index of the polynomial, and k of the coefficient. We show that, up to rescaling and renormalization, there are only five such families.

More generally, we define an auxiliary basis for the space of polynomials, called Newtonian bases, and consider coefficients with respect to this basis rather than the standard monomial basis. We call the polynomial families that satisfy the rationality conditions on ratio of successive coefficients with respect to this basis HG-families. We show that, up to rescaling, shift, and renormalization, there are only 10 quasi-orthogonal HG-families. Each family arises as a specialization of some hypergeometric series. I will define this notion in the talk. Eight of the 10 families are classical very useful polynomial families, and we view our theorem as a classification result in the theory of special functions.

We also consider the more general rational HG-families, i.e. quasi-orthogonal families in which the ratio f(n,k) of successive coefficients is allowed to be rational in n as well. I will formulate the two main theorems, one on quasi-orthogonal HG-families and one on rational quasi-orthogonal HG-families, as well as the main ideas of the proofs. They are of algebraic nature.

This is a joint work with Joseph Bernstein and Siddhartha Sahi.

Nov 11 Self-interacting walks in high dimensions Dor Elboim (Stanford University)

A self-interacting random walk is a random process evolving in an environment which depends on its history. In this talk, we will discuss a few examples of these walks including the Lorentz gas, the mirror walk, the once-reinforced walk and the cyclic walk in the interchange process. I will present methods to analyze these walks in high dimensions and prove that they behave diffusively.

The talk is based on joint works with Allan Sly, Felipe Hernandez, Antoine Gloria, Gady Kozma and Lenya Ryzhik.

Nov 18 Statistical properties of Markov shifts Yeor Hafouta (University of Florida)

The central limit theorem (CLT) and related results for stationary weakly dependent sequences of random variables have been extensively studied in the past century, starting from a pioneering work of Berenstien (1927). However, in many physical phenomena there are external forces, measurement errors and unknown variables (e.g. storms, the observer effect, the uncertainty principle etc.). This means that the local laws of physics depend on time, and it leads us to studying non-stationary sequences.

The asymptotic behaviour of non-stationary sequences have been studied extensively in the past decades, but it is still developing compared with the theory of stationary processes. In this talk we will focus on inhomogeneous Markov chains. For sufficiently well contracting Markov chains the CLT was first proven by Dobrushin (1956). Since then many results were proven for stationary chains. In 2021 Dolgopyat and Sarig proved local central limit theorems (LCLT) for inhomogeneous Markov chains. In 2022 Dolgopyat and H proved optimal CLT rates in Dobrusin’s CLT. These results closed a big gap in literature concerning the non-stationary case.

An open problem raised by Dolgopyat and Sarig in their 2021 book concerns limit theorems for Markov shifts, that is when the underlying sequence of functions that forms the partial sums depend on the entire path of the chain. Two circumstances where such dependence arises are products of random matrices and random iterated functions, and there are many other instances when the functionals depend on the entire path.

In this talk we will present our solution to the above problem. More precisely, we prove CLT, optimal CLT rates and LCLT for a wide class of sufficiently well mixing Markov chains and functionals with infinite memory. Even though the inhomogeneous case is more complicated, our results seem to be new already for stationary chains.

Dec 2 Mommy, I can’t solve this equation Dmitry Kerner (BGU)

A significant part of Mathematics boils down to “resolving systems of equations”, e.g. equations of implicit function type, F(x,y)=0. In many cases one has to resolve these just ``order-by-order”. The obtained power series, y(x), do not need to be analytic.

Artin approximation (A.P.) ensures: every formal solution is approximated by analytic solutions. This goes in contrast to various other (functional or differential) equations, for which the formal and analytic words are very different.

I will give a brief introduction to this topic, and then explain the recent results: A.P. for (quivers) of morphisms of scheme-germs. In simple words: A.P. holds for an additional class of functional equations (not of implicit function type).

Sun, Dec 7, 12:00–13:00 Negative Dependence in Tournaments, Distribution of Extreme Scores, and Uniqueness of the Maximum Yaakov Malinovsky (University of Maryland)

Negative dependence among participants’ outcomes arises naturally in probabilistic models of tournaments and plays an important role in various asymptotic results, including limit theorems, Poisson approximations, and the behavior of extremal scores. In particular, the property of negative orthant dependence has been shown in several works for different tournament models, usually requiring a separate proof in each case. In this work, we present a unified and more general approach by establishing the stronger property of negative association. This stronger notion of dependence allows us to derive limit distributions for order statistics, such as the maximum and the second-highest scores, even though their exact distributions are not available for general tournament sizes. We illustrate our approach using the round-robin tournament model (paired-comparison model in statistics). We also resolve an open problem and prove that the probability of having a unique winner tends to one as the number of players grows.

Dec 9 Virtual homological torsion in low dimensions Jonathan Fruchter (University of Bonn)

A long-standing conjecture of Nicolas Bergeron and Akshay Venkatesh predicts that in closed hyperbolic 3-manifolds, the amount of torsion in the first homology of finite-sheeted normal covers should grow exponentially with the degree of the cover as the covers become larger, at a rate reflecting the volume of the manifold. Yet no finitely presented residually finite group is known to exhibit exponential torsion growth in first homology along an exhausting chain of finite-index normal subgroups.

In this talk I will explain how a two-dimensional lens offers a clearer view of some of the underlying mechanisms that create homological torsion in finite covers, and why obtaining exponential growth may be more tractable in this setting. I will also discuss how these ideas connect to the question of profinite rigidity: how much information about a group is encoded in its finite quotients.

Dec 16 Dimension and embeddability for Dynamical systems Tom Meyerovitch (BGU)

It is well known that a compact metric space embeds in a finite-dimensional Euclidean space if and only if it has finite Lebesgue covering dimension. In 1999, Gromov introduced the notion of mean dimension, a fundamental invariant for dynamical systems that could be considered as a dynamical analogue of Lebesgue covering dimension.

A (discrete time) dynamical system is a pair (X,\Phi), where $\Phi:X\to X$ be a homeomorphism of a compact metric space $X$. The \emph{shift embeddability} or \emph{sampling-rate problem} asks: Under what conditions do there exists a finite number of continuous real-valued functions $f_1,\ldots,f_d:X \to \mathbb{R}$ so that a point $x \in X$ can be uniquely recovered by sampling the values of the $f_1,\ldots,f_d$ along the orbit of $x$?

In this talk I will describe historical developments around the shift embeddability problem and some exciting recent developments.

We will not assume any specialized background (in particular, we will recall the definition of Lebesgue covering dimension).

Dec 23 Dynamical and Dimensional Properties of Schrödinger Operators Under Finite-Rank Perturbations Netanel Levi (UCI)

In this talk, we present several dynamical and fractal-dimensional ways of characterizing the spectral measures of Schrödinger operators, such as Rajchman behavior and Hausdorff/packing dimensions, and discuss the extent to which these properties are stable under rank-one perturbations.

We begin with the concrete setting of half-line Schrödinger operators, where a theorem of Gordon shows that generic rank-one perturbations eliminate pure point spectrum, ruling out the most extreme dynamical and dimensional behavior. I will then describe constructions demonstrating that properties only slightly weaker than pure point spectrum can, in fact, be entirely stable: for certain sparse half-line models, both packing-dimension-zero and non-Rajchman behavior persist for every rank-one perturbation.

In the second part, we examine how spectral dimensions behave when passing from the whole line to the half-line. I will present an operator whose spectral measure on the line has Hausdorff dimension one, whereas every half-line restriction - under any boundary condition - has dimension zero, even though the two settings differ only by a finite-rank perturbation.

Dec 30 Creating periodic points near invariant sets Shira Tanny (Weizmann Institute)

An old question of Poincaré concerns creating periodic points via perturbations of a diffeomorphism. While this question was initially studied in the 60s, various facets of it remain largely open. Recently, several advances were made in the context of Hamiltonian diffeomorphisms, which are diffeomorphisms arising from classical mechanics. I will discuss a variant of this problem in the presence of certain invariant sets, as well as an application to invariant measures. This is based on a joint work with Erman Cineli and Sobhan Seyfaddini.

Jan 6 Ramifications of local-global compatibility in the mod p local Langlands correspondence Michael Schein (BIU)

The mod p local Langlands correspondence is expected to associate, in a functorial manner, a representation \pi(r) of the group GL_n(F) over a field of characteristic p to every n-dimensional mod p representation r of the absolute Galois group of F; here F is a p-adic field. The correspondence is only known for GL_2(Q_p). It is natural to expect it to be realized in the mod p cohomology of Shimura varieties, but any such construction of \pi(r) depends on many global choices and, apart from the case of GL_2(Q_p), is never known to depend only on r. When F is unramified over Q_p and n = 2 and r is generic, it is known that certain invariants of any \pi(r) arising in cohomology depend only on r. Moreover, Breuil has defined a functor from mod p representations of GL_n(F) to representations of the absolute Galois group of Q_p. In the above case, the known invariants of \pi(r) are enough to compute its image under the functor, which turns out to be the tensor induction of r from F to Q_p, at least up to restriction to inertia.

The talk will discuss these ideas and present some new results partially extending them to the case where F is a ramified quadratic extension of Q_p. The arguments are essentially orthogonal to those of the unramified case. A key element of the proof is the determination of (enough of) the submodule structure of mod p principal series representations of GL_2 over some finite quotients of the valuation ring of F. This structure turns out to admit a combinatorial description in terms of the columns where carries are performed when adding certain integers in base p.

The talk discusses joint works with R. Waxman and with S. Morra. Familiarity with addition with carrying will be assumed, but not familiarity with the other notions mentioned above.

Jan 13 High Dimensional Expanders and Chernoff Inequalities Yotam Dikstein (IAS)

Chernoff’s inequality is one of the most basic inequalities in probability theory. It states that the sum of independent random variables is close to its mean with very high probability. The `Expander-Graph Chernoff inequality’, proven by Ajtai, Komlos, and Szemeredi in 1987, is a powerful extension of Chernoff’s inequality, asserting that Chernoff’s inequality holds even when sampling the random variables using paths in an expander graph instead of sampling them independently.

In this talk, we will discuss further extensions and generalizations of Chernoff’s inequality coming from high dimensional expanders. High dimensional expanders are sparse hypergraphs exhibiting pseudo-random properties. These are more sophisticated structures than the expander graphs of [AKS], but in return the generalization of Chernoff’s bound obtained from them applies in a far more general setup.

We will see why Chernoff-type bounds hold for high dimensional expanders, and how this inequality arises naturally in problems in high dimensional geometry and computational complexity.

This is based on joint work with Max Hopkins. The talk will not assume prior background in complexity theory and is aimed at a broad audience.