Réunion d'hiver SMC 2023

Montréal, 1 - 4 decembre 2023


Présentations par affiches des étudiants - AARMS-SMC

KYLIAN AJAVON, Concordia University
Surrogate models for diffusion on graphs: a high-dimensional polynomial approach  [PDF]

Graphs are an essential mathematical tool used to model real-life complex systems such as social networks and transportation networks. Understanding diffusion processes on graphs is crucial for modelling phenomena such as the propagation of information within a network of individuals or the flux of goods and/or people through a transportation network. Accurately simulating these diffusion processes can be, in general, computationally demanding since it requires the solution of large systems of ordinary differential equations.

Motivated by this challenge, we propose to construct surrogate models able to approximate the state of a graph at a given time from the knowledge of the diffusivity parameters. Specifically, we consider recently introduced high-dimensional approximation methods based on sparse polynomial expansions, which are known to produce accurate, sample-efficient approximations when the function to be approximated has holomorphic regularity. Hence, to justify our methodology, we will theoretically show that solution maps arising from a certain class of parametric graph diffusion processes are indeed holomorphic. Then, we will numerically illustrate that it is possible to efficiently compute accurate sparse polynomial surrogate models from a few random samples, hence empirically showing the validity of our approach.

OSAMA BATAINEH, Univ. of Saskatchewan
Imprecise Probabilities for Cryptanalysis of Ciphertexts  [PDF]

In cryptography, secrecy of ciphertext decryption is important and crucial for protection against cipher cyber-attacks. In ciphertext decryption, the appropriate probabilistic model must be selected to measure on occurrences of ciphertext characters. In this poster, imprecise probabilities are used to reflect the differences in prior beliefs amongst cryptanalysts, on probabilities of occurrences of alphabetic characters in ciphertexts. They can be used to give larger margin for predicting the correct keywords for successful decryption of difficult ciphertexts. For each character, there will be lower and upper bound probabilistic estimates based on using Bayesian methods with sets of prior distributions. It is important to see how prior changes, based on imprecise probability models, can impact changes in posterior distributions of ciphertexts, and their decryptions. Furthermore, imprecise probabilities can establish for new understanding of concepts of "perfect secrecy", "redundancy" and "unicity distance" in ciphertext decryption procedures.

JERMEY CHIZEWER, University of Waterloo
Enumeration and Compact Encoding of AVL Trees  [PDF]

An AVL tree is a type of self-balancing binary search tree commonly used in computer science. From an enumerative perspective, an AVL tree is a rooted planar binary tree such that the heights of the left and right subtrees at any node differ by at most one. Because AVL trees are most easily recursively decomposed by height instead of by number of nodes, their enumeration is more difficult than other classes of recursively defined trees.

Motivated by a desire to derive the information-theoretic lower bound on the number of bits needed to encode an AVL tree, we develop a new method for the study of combinatorial classes whose generating functions satisfy certain functional equations and use this tool to derive the growth rate of AVL trees and related structures. We also describe a new encoding for AVL trees that uses less than one bit per node.

Joint work with Stephen Melczer, J. Ian Munro, and Ava Pun.

SAYANTAN ROY CHOWDHURY, University of Western Ontario
Essential dimension of symplectic vector bundles over a curve  [PDF]

Essential dimension of an algebraic object, introduced by J.Buhler and Z.Reichstein, is defined as the minimal number of algebraic variables needed to parameterize the object. The essential dimension of a moduli stack is defined as the the supremum of the essential dimension of objects it parameterizes. This number can be computed only in a handful of cases. In general, bounds are hard to obtain, however Dhillon, Hoffmann and Biswas obtained such an upper bound for vector bundles over a smooth projective curve.

In this poster, we generalise these results in the case of symplectic vector bundles. The essential dimension of a symplectic vector bundle can be broken into two terms, namely the transcendence degree of its field of moduli and the essential dimension of the bundle over its field of moduli. We show that the first part can be related to the essential dimension of hermitian modules over an algebra, while the second part can be bounded by the dimension of moduli stack of symplectic vector bundles equipped with nilpotent morphism of symplectic type. We prove that the latter object is smooth and hence its dimension can be computed by a Riemann-Roch formula.

DANIEL DALLAIRE, University of Ottawa
The Chromatic Category: A Connection Between Planar Graph Colouring And Representation Theory  [PDF]

The chromatic category is a diagrammatic monoidal category which encodes information about the colourings of planar graphs. Although it has a direct relation to graph theory in this way, it can also be constructed in a representation theoretic context yielding an interesting connection between the problem of colouring planar graphs (in particular, the four colour theorem) and representation theory. In this work I explore these connections and prove results about the chromatic category. One main result is that this category is isomorphic to a category of representations of quantum $\mathfrak{sl}_2$, which in the 4-colour case, tells us the category is equivalent to a category of representations of (non-quantum) $\mathfrak{sl}_2$. In addition to this, I give bases for the morphism spaces in the category, discuss the category's relation to the well-known Temperley-Lieb category, and show that it is pivotal (allowing for topological arguments on the morphisms). Lastly, I give different presentations of the category, all of which are isomorphic to the chromatic category.

The Saturn Ring Defect for Two Colloidal Particles  [PDF]

The study of nematic liquid crystals and the defects that arise due to various energy configurations has been of great interest to both mathematicians and physicists alike. In particular, it has been shown in the physics literature that there are several varieties of line defects which can be studied using a plethora of mathematical and physical models. In their 2016 paper, Alama, Bronsard & Lamy showed, using the Landau-de Gennes model for liquid crystals in a particular regime, that for a single spherical colloid immersed within such a nematic material, a ring defect is formed when the particle is sufficiently small, called the 'Saturn ring defect'. They also showed that the defect is formed at the positions where there is an exchange of the dominant eigenvalues from the $Q$-tensor. This tensor is the solution to the Laplace equation with Dirichlet boundary conditions on the particle. In this poster presentation, we will summarize the mathematics behind the Saturn ring defect, and we will present our extended problem analyzing the ring defect(s) that may arise for two colloidal particles. We will describe how, in this case, changing the domain to bispherical coordinates allows us to obtain an analytic solution for the $Q$-tensor. We will conclude by demonstrating how we can use our series solution to explicitly and numerically map the structure of the defects in the planar region situated exactly halfway between the colloids. We will also pinpoint the locations of the dominant eigenvalues and find where they cross.

SARAH LUCKY, Lakehead University
Actions of certain finite groups on lattice ordered dimension groups  [PDF]

Following the classification via K-theory of AF $C^*$-algebras by Elliott, the complementary range of invariant problem was solved by Effros, Handelman, and Shen when they characterized those partially ordered abelian groups that arise as inductive limits of simplicial groups. Later work by Elliott and Su led to the question of when a group action on a dimension group arises as an inductive limit of actions on simplicial groups. Work of Choi and Dean gave a partial answer in the case of ${\Bbb Z}_2$ actions. The present work extends their results to actions of more finite groups.

MARCO MIGNACCA, McGill University
Motion Detection Using Dynamic Mode Decomposition  [PDF]

Dynamic Mode Decomposition (DMD) is a numerical method that seeks to fit timeseries data to a linear dynamical system. In doing so, DMD decomposes dynamic data into spatially coherent modes that evolve in time according to exponential growth/decay or with a fixed frequency of oscillation. A key example of timeseries data that DMD has been applied to are videos, where one interprets the high-dimensional pixel space evolving through time as the video plays. In this work, we propose a simple, interpretable motion detection security system for video firmly rooted in DMD. Our method leverages the idea that there exists a correspondence between the evolution of important video features (encoded in the coherent spatial modes) and the eigenvalues of the matrix resulting from DMD. Precisely, our method applies DMD to windowed subsets of the video, which allows one to localize disturbances in the frames by observing the dominant timescales present in the modes. The effectiveness of the algorithm in detecting motion in the video is measured through an analysis based on receiver operating characteristic (ROC) curves. Performance of the motion detection algorithm is optimized for a given dataset of training videos based on k-fold cross-validation.

SINA MOHAMMAD-TEHERI, Concordia University
Greedy deep unfolding: New neural networks based on sparse recovery algorithms  [PDF]

In recent years, \emph{algorithm unfolding} (or \emph{unrolling}) has emerged as a promising methodology in various signal-processing applications, notably in biomedical imaging. It aims to combine the strengths of sparse recovery and deep learning by designing deep neural network architectures that implement the iterations of an iterative algorithm as network layers. Despite its success, unfolding \emph{greedy} sparse recovery algorithms like Orthogonal Matching Pursuit (OMP) or Compressive Sampling Matching Pursuit (CoSaMP) has received little attention. The primary challenge is the non-differentiable nature of the argsort operator, a key component in greedy algorithms, which hinders gradient backpropagation during training.

To address this, our work introduces a novel approach, termed `greedy deep unfolding'. We utilize \emph{soft sorting} to approximate the argsort operator in a differentiable manner. Additionally, we reinterpret greedy algorithms through a projection-based lens and approximate the permutation matrices from argsort with stochastic matrices derived from soft sorting. Our numerical and theoretical analyses show that under certain conditions, the approximation error is minimal, and the performance of the approximated greedy algorithm closely matches the original. We then incorporate this approximate algorithm into a feedforward neural network's layers, integrating learnable \emph{weight} parameters to connect to weighted sparse recovery. Our numerical results demonstrate that this network is trainable and can surpass the performance of the traditional approximate greedy algorithm in certain scenarios.

KATE NIMEGEERS, University of Victoria
Pseudoku: A Sudoku Adjacency Algebra and Fractional Completion Threshold  [PDF]

We develop a new $4$-partite graph representation, $G_P$, for a partial Sudoku, $P$. In this representation, partite sets correspond to the rows, columns, boxes, and symbols of $P$. The edges represent unfulfilled conditions in $P$ that are necessary for a completed Sudoku. For instance, if symbol $3$ is missing from the first row in $P$, an edge is drawn between those vertices in $G_P$. We define a tile to be a $4$-vertex subgraph of $G_P$ corresponding to a valid placement of a symbol in $P$. We note that $P$ can be completed if and only if its graph representation $G_P$ has an edge-decomposition into tiles. We then relate the existence of a tile-decomposition to the existence of a solution to a specific linear system using an edge-tile inclusion matrix. Through an in-depth analysis of this matrix structure, we uncover a Sudoku adjacency algebra. This algebraic framework is constructed from a coherent configuration, comprised of equivalence relations among row-column, row-symbol, column-symbol, and box-symbol Sudoku conditions.

The result we present is a degree threshold for $G_P$ that allows a fractional tile-decomposition, implying the existence of a fractional completion of $P$. The proof employs spectral decomposition, the properties of coherent configurations, and perturbation theory to estimate a generalized inverse for the matrix representation of a partial Sudoku puzzle in order to find a solution for the relaxed linear system. Improving on this result by finding a minimum degree threshold for an exact tile-decomposition is an interesting open question in this research area.

ERIC SUI, Carleton University (Math Enrichment Centre)
On Intersections of Hyperplanes Formed by $n$ Points in Low-Dimensional Space  [PDF]

This research poster explores discrete geometry, a field laden with aspects of not only geometry, but also combinatorics. It focuses on the counting of intersections in various dimensions, with a focus on the second and the third. We are given $n$ points in $k$ dimensional space. We form hyperplanes ($k-1$ dimensional objects) which are determined by $k$ of the $n$ points. How many unique $k-2$ dimensional intersections of these hyperplanes exist? In this poster, we solve a simple combinatorial geometry problem as a precursor. This problem is defined in 2-dimensions and it is also focused on the formation of objects from points. Then, we solve the 2 dimensional and 3 dimensional cases using purely combinatorial techniques and provide diagrams for each of these cases. Further exploration would entail how we can solve this problem in $4$ or higher dimensions. Possible approaches could be an inductive process involving lifting the points or a similar combinatorial approach for higher dimensions.

SILAS VRIEND, McMaster University
The standard lens cluster in $\mathbb{R}^2$ uniquely minimizes relative perimeter  [PDF]

We present a new type of planar partitioning problem in which one minimizes perimeter among clusters with one domain of finite area and two of infinite area. This generalizes the classical setting where one minimizes perimeter among clusters with a fixed number of domains of finite prescribed area. The classical isoperimetric problems have led to the famous double and triple bubble conjectures, which have both been proven to hold in the Euclidean plane. We use the planar double bubble theorem to show that the lens cluster is the unique minimizer for the isoperimetric problem of partitioning the plane into three disjoint domains, one having unit area and the remaining two having infinite area. In addition to the result, we present a general framework and several conjectures for this new class of problems in geometric measure theory.

ARTHUR WESLEY, Dalhousie University
On Quantum Circuits Enacting the E8 Weyl Group  [PDF]

The circuit diagrams studied in computer science enjoy a rich mathematical theory. Starting from a finite set of primitive operators known as "gates", a circuit diagram is any operator obtained by composing a finite number of gates in sequence or in parallel. A special class of circuit diagrams are the classical reversible circuits, in which gates are invertible matrices over $\mathbb{Z}_2$. It was shown by Toffoli in 1980 that every classical reversible circuit is constructible from a single primitive known as the Toffoli gate, given sufficiently many ancillas (i.e., working memory). Later, Feynman generalized classical reversible circuits to quantum mechanical systems in which invertible matrices are replaced by unitary matrices. Since unitary matrices are uncountable, there does not exist an exact universal gate set for quantum computation. However, given both the Toffoli gate and Hadamard gate, all unitary operators can be simulated.

In this poster, we describe ongoing work to obtain a minimal presentation for the group $G$ of 3-qubit ancilla-free Toffoli+K circuits (where K is the two-fold tense of a Hadamard gate). From prior results in sphere packings, it follows that $G$ is isomorphic to the E8 Weyl group. We start from the Coxeter presentation of this Weyl group and obtain a circuit presentation using a semantic variation of Tietze transformations. We use commutativity relations to prove generator minimality and implement a proof-assistant to validate each semantic transformation. Directions for future work, such as minimizing the set of relations and generalizing to the 3-qubit ancilla-free Toffoli+K circuits, are outlined.

WILLIAM ZHANG, Concordia University
Broadcasting in NetworkX  [PDF]

Broadcasting is an information disseminating problem in a connected network of transmitting a message from an originator vertex to all other vertices as quickly as possible. It is well known that finding the broadcast time for any random vertex in an arbitrary graph is NP-complete. However, it has been proven that this problem can be solved in polynomial time for a certain class of graphs. The dissemination process is as follows; the originator begins by placing a series of calls along the communication lines of the network. Every time the informed nodes help the originator in distributing the message. Every call is assumed to take place in discrete units of time. The broadcasting must be completed as quickly as possible subject to some constraints. This talk will demonstrate implementations of a broadcasting algorithm using the open-source graph library NetworkX. In addition, other related topics such as broadcast graphs and the design of efficient networks will be covered.

SICHENG ZHAO, Queen's University
Disease Spread on Networks using Percolation Methods and Edge-Based Modeling  [PDF]

Bond percolation methods can be used to model disease transmission on complex networks and accommodate social heterogeneity while keeping tractability. Here we review the seminal works on this field by Newman (2002, 2003, 2010), and Miller, Slim & Volz (2011) and present a more clear and systematic discussion about the theoretically background, assumptions, derivation and development of the percolation method. We also present a new R package based on these papers that take epidemic and network parameters as input and generates estimates of the epidemic trajectory and final size. This allows us to investigate the interaction between different community structures and disease control strategies, leading to interesting new research directions.

© Société mathématique du Canada : http://www.smc.math.ca/