Dynamics and Probability Seminar Spring 2024

The Dynamics and Probability seminar will meet on Tuesday afternoons at 2:30 in DSB C114, or on Zoom when the speaker is not present in Victoria. All are welcome. Please contact Anthony Quas for the zoom link. The list of seminars is as follows. For further information, please contact me at aquas(a)uvic.ca or Gourab Ray at gourabray(a)uvic.ca

Date Speaker Title

16/1/2024 Anthony Quas (UVic) Gaps between Lyapunov exponents

23/1/2024 Gourab Ray (UVic) Minimal spanning arborescence

30/1/2024 Ronnie Pavlov (Denver) Subshifts with very low word complexity

6/2/2024 Sajin Koroth (UVic) Understanding the lifting phenomena (exporting our understanding from weak models of computation to strong models) and the underlying pseudo-random properties

13/2/2024 Eric Foxall (UBCO) Some uses of ordered representations in finite-population exchangeable ancestry models

27/2/2024 Partha Dey (UIUC) .

5/3/2024 Benoit Corsini (Eindhoven) Local weighted optimizations and open problems

12/3/2024 Te-Chun Wang (UVic) .

19/3/2024 Tamara Kucherenko (New York) .

26/3/2024 Agnieszka Zelerowicz (UC Riverside) ..

2/4/2024 Yu-Ting Chen (UVic) .

Date: 16/1/2024
Speaker: Anthony Quas (UVic)
Title: Gaps between Lyapunov exponents
Abstract: We consider an arbitrary sequence of d*d matrices (A_n) of norm at most 1 and subject them to noiselike perturbations of size epsilon. We show that the perturbed system has simple Lyapunov spectrum (no repeated exponents) and give universal bounds on gaps between exponents as a function of d and epsilon.

Date: 23/1/2024
Speaker: Gourab Ray (UVic)
Title: Minimal spanning arborescence
Abstract: I will talk about the `minimal spanning arborescence', a directed version of the Minimal spanning tree. I will explain how this naturally leads to a new type of stochastic process which we call `loop contracting random walk'. I will show how this can be analyzed in the setting of trees. I will finish with some simulations and open questions. Joint work with Arnab Sen.

Date: 30/1/2024
Speaker: Ronnie Pavlov (Denver)
Title: Subshifts with very low word complexity
Abstract: The word complexity function p(n) of a subshift X measures the number of n-letter words appearing in sequences in X, and X is said to have linear complexity if p(n)/n is bounded. It’s been known since work of Ferenczi that linear word complexity highly constrains the dynamical behavior of a subshift. In recent work with Darren Creutz, we show that if X is a transitive subshift with limsup p(n)/n < 3/2, then X is measure-theoretically isomorphic to a compact abelian group rotation. On the other hand, limsup p(n)/n = 3/2 can occur even for X measurably weak mixing. Our proofs rely on a substitutive/S-adic decomposition for such subshifts. I’ll give some background/history on linear complexity, discuss our results, and will describe several ways in which 3/2 turns out to be a key threshold (for limsup p(n)/n) for several different types of dynamical behavior.

Date: 6/2/2024
Speaker: Sajin Koroth (UVic)
Title: Understanding the lifting phenomena (exporting our understanding from weak models of computation to strong models) and the underlying pseudo-random properties
Abstract: Lifting theorems have played a key role in many recent breakthrough results in diverse areas of theoretical cs and mathematics via simple yet profound connections between these areas and communication complexity. A typical lifting theorem translates the query complexity (a very simple model of computation) of a Boolean function to the communication complexity (a more powerful model) of an associated function obtained by a central operation of Boolean functions known as block-composition by composing with another function known as inner function. Most lifting theorems work for any Boolean function f and depend upon the pseudo-random properties of the inner function g known as the gadget. The main parameter of efficiency in lifting theorems is the input size of the inner function g. Obtaining lifting theorems for constant-sized gadgets would give us breakthrough results and a nearly complete understanding of lifting phenomena; current techniques are far from achieving this goal. The main barrier is the existence of “nice” pseudo-random properties for well-known gadgets when their input length is relatively small compared to the outer function. Recent results have shown that understanding the psudo-random properties is inherently connected to interesting questions in combinatorics (like the sunflower lemma) and in Boolean function analysis. In this talk, we will go through a high level overview of lifting theorems and the necessary condition that enable lifting phenomenon. We will also see some applications of lifting theorems in diverse areas of theoretical cs and mathematics, achieved via surprising yet simple connections. We will also go over recent advances in understanding the pseudo-random properties that drive the lifting phenomena and important barriers and open problems related to this.

Date: 13/2/2024
Speaker: Eric Foxall (UBCO)
Title: Some uses of ordered representations in finite-population exchangeable ancestry models
Abstract: For a population model that encodes parent-child relations, an ordered representation is a partial or complete labelling of individuals, in order of their descendants’ long-term success in some sense, with respect to which the ancestral structure is more tractable. The two most common types are the lookdown and the spinal decomposition(s), used respectively to study exchangeable models and Markov branching processes. We study the lookdown for an exchangeable model with a fixed, arbitrary sequence of natural numbers, describing population size over time. We give a simple and intuitive construction of the lookdown via the complementary notions of forward and backward neutrality. We discuss its connection to the spinal decomposition in the setting of Galton-Watson trees. We then use the lookdown to give sufficient conditions on the population sequence for the existence of a unique infinite line of descent. For a related but slightly weaker property, takeover, the necessary and sufficient conditions are more easily expressed: infinite time passes on the coalescent time scale. The latter property is also related to the following question of identifiability: under what conditions can some or all of the lookdown labelling be determined by the unlabelled lineages? A reasonably good answer can be obtained by comparing extinction times and relative sizes of lineages.

Date: 27/2/2024
Speaker: Partha Dey (UIUC)
Title:
Abstract:

Date: 5/3/2024
Speaker: Benoit Corsini (Eindhoven)
Title: Local weighted optimizations and open problems
Abstract: In this talk, I will present a recent work in which two co-authors and myself studied the behaviour of a local algorithm optimizing the weight of a graph. More precisely, the process starts with a given subgraph H of the complete graph with uniform weights and a maximal weight W, and inductively replaces a subgraph of H and of weight less than W by the minimum spanning tree on the corresponding set of vertices. Our main result shows that there is a sharp threshold for W regarding the asymptotic behaviour of this algorithm (i.e. with high probability): if W is less than 1, it is impossible to reach the global minimum spanning tree, whereas it is possible when W is larger than 1. Since this work introduces a new type of local algorithm, I will also present some related open problems. In particular, our results prove when such algorithms can reach the global minimum spanning tree and it is then only natural to ask how fast they can do so when possible. The answer to this question actually relates to efficiently packing sets of uniforms into a special type of partition and leads to a surprisingly difficult open question.

Date: 12/3/2024
Speaker: Te-Chun Wang (UVic)
Title:
Abstract:

Date: 19/3/2024
Speaker: Tamara Kucherenko (CCNY)
Title:
Abstract:

Date: 26/3/2024
Speaker: Agnieszka Zelerowicz (UC Riverside)
Title:
Abstract:

Date: 2/4/2024
Speaker: Yu-Ting Chen (UVic)
Title:
Abstract:

For (some) previous semesters, see