Supervisor: Dr. Kevin Cheung, Carleton University

Project Overview

A polynomial can be expressed as a sequence of additions and multiplications of two terms, each of which can be a variable, number, or what has been computed so far. Note that the same polynomial can be computed in different ways using different numbers of operations. For example, xy+xz takes three operations. But the equivalent x(y+z) takes only two. The study of how few operations are required appears in computational complexity theory as arithmetic circuit complexity. The focus on the project, however, is on the practical aspects of actually finding optimal arithmetic circuits.

Detailed Description

A polynomial can be expressed as a sequence of additions and multiplications of two terms, each of which can be a variable, number, or what has been computed so far. Note that the same polynomial can be computed in different ways using different numbers of operations. For example, xy+xz takes three operations. But the equivalent x(y+z) takes only two. The study of how few operations are required appears in computational complexity theory as arithmetic circuit complexity. A brief introduction to the topic of arithmetic circuit complexity can be found in Wikipedia: https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity

The focus on the project is on the practical aspects of actually finding optimal arithmetic circuits since arithmetic circuits arise in computation graphs in applications such as machine learning and automatic differentiation. Quite often, heuristics are employed to obtain a good scheme for the ordering of computations. The backward mode in automatic differentiation (or backpropagation in machine-learning lingo) is an example. Given that the problem is NP-complete (see [1]), it is unlikely that there exists a polynomial-time algorithm. Nevertheless, clever use of mathematical programming techniques might prove effective in solving small-sized instances as evidenced by success in a remotely-related problem of finding optimal sparse decision trees [2].

For the project, students will review relevant literature in arithmetic circuits and mathematical programming. Students will brainstorm algorithmic ideas and come up with implementations for testing purposes. Students will report final results.

References

1. U. Naumann, Optimal Jacobian accumulation is NP-complete, Mathematical Programming 112, pp.427-441, 2008.
2. X. Hu, C. Rudin, M. Seltzer, Optimal sparse decision trees, NeurIPS 2019.

Supervisor: Dr. Anthony Bonato, Ryerson University

Project Overview

In graph searching, we consider simplified, combinatorial models for the detection or neutralization of an adversary's activity on a network. The most studied such game is Cops and Robbers, where the cops attempt to capture the robber by prescribed rules. We will consider a new variant of Cops and Robbers called the localization game, where the robber is invisible but we have partial information on its whereabouts. We will study the localization game on graphs derived from combinatorial designs and models for social networks.

Detailed Description

In graph searching, we consider simplified, combinatorial models for the detection or neutralization of an adversary's activity on a network. Such models often focus on vertex-pursuit games, where agents or cops are attempting to capture an adversary or robber loose on the vertices of a network. The players move at alternating ticks of the clock and have restrictions on their movements or relative speed depending on the type of game played. The most studied such game is Cops and Robbers, where the cops and robber can only move to vertices with which they share an edge. The minimum number of cops needed to capture the robber in a graph G is the cop number of G, written c(G). Cops and Robbers and its variants form an emerging topic in graph theory, with new results rapidly appearing in the literature.

The localization game played on graphs is a variant of Cops and Robbers, where the robber is invisible, but the cops may send distance probes that return the graph distance from their position to the robber. The localization game is motivated by real-world tracking problems such as pinpointing cell phone users via mobile receivers. The cops may move to any vertex of the graph each round, while the robber moves from vertex-to-vertex along edges. The cops win if they can determine the exact position of the robber; otherwise, the robber wins. Placing cops on each vertex ensures a win for the cops, so we may define the localization number of G, written ζ(G), to be the least integer for which the cops have a winning strategy over any possible strategy of the robber (that is, we consider the worst-case that the robber a priori knows the entire strategy of the cops.

There is a small but rapidly growing set of results on the localization number. Previous work has shown that ζ(G) is bounded above by the pathwidth of G and that the localization number is unbounded even on graphs obtained by adding a universal vertex to a tree. Computing ζ(G) is NP-hard for graphs with diameter 2. Connections have been found between the localization number and the chromatic number, and the parameter has been studied for outerplanar graphs and hypercubes.

The localization number of the incidence graphs of designs was studied by Bonato and others. In particular, they gave exact values for the localization number of the incidence graphs of projective and affine planes, and bounds for the incidence graphs of Steiner systems and transversal designs. An interesting problem to explore is to consider the localization number for graphs derived from Latin Squares. What bounds or exact values for ζ(G) can be found for such graphs? The problem is sufficiently open-ended to allow for many partial results and would require only elementary methods from Latin squares and combinatorial designs. My post-doc Trent Marbach is an expert on Latin squares and will help guide this research.

Another direction is to consider the localization number for models of social networks. In 2004, I introduced the Iterated Local Transitivity (ILT) model, which provably simulates many of the properties observed in social networks, such as the small-world property, densification, and bad spectral clustering. The ILT model is deterministic and straightforward to define, but leads to complicated graph dynamics. The model replicates the graph structure of an initial graph over discrete time-steps. A good problem with an achievable solution would be to analyze the localization number in the ILT model, relating it back to the localization number of the initial graph. Variants of the ILT model exist for directed graphs and hypergraphs, and a broader goal would be to analyze the localization number and related parameters for such variants.

Supervisor: Prof. Alec Jacobson, University of Toronto

Project Overview

In this project, we will investigate the signed distance field representation for 3D solid shapes. These representations are powerful in computer graphics and recently machine learning. We will study how to project messy or erroneous near-signed distance fields into exact signed distance fields. This project has interesting connections to differential geometry, partial differential equations, optimization and machine learning.

Detailed Description

Surfaces of three-dimensional solids can be represented _implicitly_ as the set of points for which some function f : R^3->R evaluates to zero. This representation is incredibly useful for digital geometric modeling and computer graphics. Recently, signed distance fields have surged in importance due to success representing these functions with neural networks from machine learning. An important special case is when f evaluates the "signed distance field" (SDF) of the surface: for a query point x, f returns the distance to the closest point on the surface multiplied by +1 or -1 if the point x is outside or inside the surface, respectively. Exact SDFs satisfy the Eikonal equation (unit-norm gradient almost everywhere) and the condition that the gradient points along a line containing the closest point. This structure enables fast rendering in graphics and fast distance querying for collision handling in physics-based simulation. Unfortunately, most "SDF"s in the wild are only _approximate_-SDFs and fail to meet the conditions above.

In this project, we will investigate methods to convert approximate-SDFs into proper exact-SDFs. To do this, we must first understand the "space of SDFs" and its relationship to the space of 3D shapes. It is already known that not all apparent solutions to the Eikonal equation are SDFs, so we must expand on this necessary condition to find additional necessary conditions (or ideally identify sufficient conditions). We will model the projection of a noisy or erroneous SDF-like function to the space of proper SDFs as an optimization problem which we then discretize on the computer.

After an introduction to the related literature in the first week of the summer, students will begin implementing signed distance fields in two dimensions and evaluating techniques for projecting SDF-like functions into proper SDFs. The middle weeks will be spent generalizing to more complex functions (e.g., neural network representations) and to SDFs in three dimensions. The final weeks will be split between optimizing the computational performance of our methods and preparing a report on the summer's work.

The students undertaking this project will not only work on novel research with the intent to publish an academic paper, but will also have the opportunity to become familiar with the computer graphics and geometry processing scientific literature. This project will gather topics in numerical methods, sparse linear algebra, partial differential equations and computational geometry. In addition, the student will be invited to join the Dynamic Graphics Project (dgp) at the University of Toronto, Department of Computer Science, where we host weekly seminars and group research discussions with graduate students.

Final Report

Supervisor: Dr. Angel David Martínez Martínez, University of Toronto
Co-Supervisor: Dr. Francisco Torres de Lizaur, University of Toronto

Project Overview

The project sits at the intersection of mathematical analysis, physics and differential geometry. Broadly speaking the object of study will be the eigenfunctions of the laplacian on a manifold. In the easiest case, the circle, these reduce to the complex exponentials which connects the questions with Fourier analysis and shows their importance. For other manifolds, such as the tori, they are well studied objects for which many fundamental properties remain unveiled.

In this project we expect the students to gradually get acquainted with the elementary analysis and working knowledge around these objects and a basic understanding of the main open questions in the field. Not surprisingly, this project cast many shadows from number theory, complex analysis, special functions or probability.

Detailed Description

One of the basic properties of eigenfunctions con a compact manifold is that the volume of points where they assume positive values is proportional to the volume where they assume negative values, with constants independent of the eigenvalue. The symmetry conjecture asserts that this result of Donelly and Fefferman can be improved in the semiclassical limit as the eigenvalue increases so that the constant is asymptotically one.

The supervisors of this project have recently proved this conjecture to be true for a certain family of manifolds and false in general. Some intriguing questions, though, remain open. The negative results are attained by a combination of mathematical analysis and a computer assisted argument.

No prior knowledge is needed. The research part of the project might require some experience programming. We expect the students to be able to program C++ or SAGE. A solid background on analysis might be useful as well, otherwise this project will be a good excuse to get it.

Students will start the project talking to their advisors that will suggest some basic reading depending on their background. After learning the necessary background, they will move to the frontier of knowledge where numerical experiments might provide some insight of the situation. Students will spend the remaining time tackling some of the open problems we propose, making their own conjectures and writing up their results. It might lead to a research level article at the end.

Supervisor: Prof. Florian Shkurti, University of Toronto

Project Overview

Safe exploration presents a major challenge in reinforcement learning (RL): when active data collection requires deploying partially trained policies/controllers, we must ensure that these policies avoid catastrophically unsafe regions, while still enabling trial and error learning. We propose to augment safe exploration with a learned model of the dynamics, as well as with a state representation scheme that enables fast adaptation to encountering an unsafe state, so that the agent can quickly learn to adapt.

Detailed Description

Reinforcement learning (RL) is a powerful framework for learning-based control because it can enable agents to learn to make decisions automatically through trial and error. However, in the real world, the cost of those trials – and those errors – can be quite high: an aerial robot that attempts to fly at high speed might initially crash, and then be unable to attempt further trials due to extensive physical damage. However, learning complex skills without any failures at all is likely impossible. Even humans and animals regularly experience failure, but quickly learn from their mistakes and behave cautiously in risky situations.

Our goal is to develop safe exploration methods for RL that similarly exhibit conservative behavior, erring on the side of caution in particularly dangerous settings, and limiting the number of catastrophic failures. A number of previous approaches have tackled this problem of safe exploration, often by formulating the problem as a constrained Markov decision process (CMDP) (Garcıa & Fernandez, 2015; Altman, 1999). However, most of these approaches require additional assumptions, like assuming access to a function that can be queried to check if a state is safe (Thananjeyan et al., 2020), assuming access to a default safe controller (Koller et al., 2018; Berkenkamp et al., 2017), assuming knowledge of all the unsafe states (Fisac et al., 2019), and only obtaining safe policies after training converges, while being unsafe during the training process (Tessler et al., 2018; Dalal et al., 2018).

Together with one of my graduate students, the undergraduate students will extend a reinforcement learning method that we have recently developed here https://arxiv.org/abs/2010.14497. The students will be responsible for understanding the theory as well as run simulation experiments for validation. The project will begin May 2021 and will end August 2021, with the option that the students continue the research if they wish to.

Supervisor: Prof. Masoud Khalkhali, Western University
Co-Supervisor: Prof. Asghar Ghorbanpour, Western University

Project Overview

A trace formula is an identity that involves two sets of very different kinds of numbers. On one side, it involves geometry and on the other side, it collects spectral information. It can be expressed in a prototypical form as
\sum \text{geometric terms} = \sum \text{spectral terms}.
A simple example is
\sum a_{ii} =\sum \lambda_i
which expresses the sum of eigenvalues of a matrix as the trace of the matrix.

Spectral terms are usually hard to calculate, and involve representation theory of groups, and eigenvalues of Laplacians. Nevertheless trace formula allows to compute certain weighted sums of these eigenvalues in terms of the geometry of the group and its conjugacy classes. The Poisson summation formula and its nonableian version, the Selberg trace formula, are examples of trace formulas. The Poisson summation formula can be used to prove a functional equation for theta functions and then the functional equation for Riemann zeta functions. The Selberg trace formula was used by Selberg to prove a prime geodesic theorem and a Riemann hypothesis for the Selberg zeta function of hyperbolic Riemann surfaces. In physics a trace formula signals a deep relation between classical dynamics and its quantum analogue as a correspondence principle.

Detailed Description

Trace formulas can be adapted to finite, and some infinite graphs, as well as some finite nonabelian groups and as such have found many applications to counting problems involving graphs. The results for graphs and finite groups are usually more combinatorial, less analytic, and easier to prove.This project requires a good background in linear algebra and basic undergraduate analysis and group theory.

Students will start by learning about Poisson summation formula and some of its implications to geometry, theta functions, and lattice counting problems. They will then move to the discrete and finite setting of finite graphs and finite groups. They will learn about graph Laplacians, Ihara zeta functions for graphs and Selberg trace formulas for graphs and groups. The two books by Audrey Terras (Zeta Functions of Graphs, and Fourier Analysis on Finite Groups and Applications) and references therein are excellent sources. After this initial training stage, the students will start by identifying terms in the trace formula for specific groups in terms of special functions like Bessel functions. They will try to conjecture a suitable form of the trace formula for infinite discrete groups. We plan to look for explicit heat kernel expressions for graph Laplacians as well. We shall be interested in quantum chaos and relations to random matrix theory also.

Supervisor: Prof. Lyle Muller, Western University
Co-Supervisor: Prof. Ján Mináč, Western University

Project Overview

Random graphs provide powerful descriptions of network structure and dynamics. In this project, we will train a recurrent neural network to perform a variety of cognitive tasks. We will then characterize the network structure of the connections between neurons. By testing for common structures that repeatedly appear upon following training, we will identify structures that contribute to specific computations. We will then develop analytical approaches to describe these network structures and to investigate how these structures can be used for neural computation. This work will be done in collaboration with the research group of Ján Mináč (Department of Mathematics, Western University), with the potential to collaborate with colleagues in systems neuroscience.

Detailed Description

In this project, we will study the connection between network structure and computation. Following recent work (Yang et al., Nature Neuroscience 22, 2019), we will train recurrent neural network (RNN) models on working memory, decision making, and categorization tasks. We will characterize the structure of the resulting networks using standard graph-theoretic measures. By repeatedly training these models and characterizing the resulting network, we will aim to describe consistent structures that contribute to success in each task. We will then aim to study the resulting network structures using a recently developed analytical approach.

Theoretical investigations of random graph models generally apply asymptotic methods to obtain mathematical expressions for network measures in the limit of infinite system size. While these methods have provided much insight into network structure at large scales, they can obscure the fine-scale structure in recurrent network models, which typically consist of only hundreds or thousands of nodes. In previous work, we have developed an operator-based approach to calculate algebraically well-defined graph-theoretical measures in network models at finite scale (Rudolph-Lilith and Muller, Physical Review E, 2014). We will extend this approach to study structure in weighted graphs and analyze structures that repeatedly appear in RNNs trained on cognitive tasks.

Results from this research can provide insight into the connection between structure and computation in RNN models, in addition to the mechanisms underlying working memory processes in the brain. This work will occur within a collaborative group at the Departments of Mathematics and Applied Mathematics at Western University; in addition, students will have the opportunity to collaborate with colleagues in systems neuroscience.

Supervisor: Dr. Ada Chan, York University
Co-Supervisors: Prof. Christino Tamon, Clarkson University, Prof. Xiaohong Zhang, University of Waterloo

Project Overview

Quantum walk on graphs is a generalization of random walk on graphs. With the emergence of quantum computing, quantum walk has found applications in both quantum information and quantum computation. In quantum information, quantum walk has been important for studying information transfer and entanglement generation in quantum networks. In quantum computation, the fundamental Grover search algorithm is a quantum walk on the complete graph. The latter observation has been the basis of subsequent development of various quantum algorithms.

In this project, we focus on state transfer in continuous-time quantum walk. The goal is to arrange for the quantum walk to transform an initial quantum state to a target quantum state. This naturally generalizes classical notions such as hitting time and mixing times in random walk on graphs. By the quantum mechanical laws defined by Schrodinger's equation, we propose to investigate quantum walk on graphs whose connectivity structure are described by complex Hermitian matrices. Our main goal is to understand the power and limitations of employing complex weights for quantum walk on these graphs.

Detailed Description

In quantum information, the well-known monogamy of entanglement property states that it is not possible to share entanglement between more than two parties. A similar monogamy property is known for perfect state transfer in quantum walk on graphs with real symmetric adjacency matrix. But, there are known violations of this monogamy property for quantum walk on graphs with complex Hermitian adjacency matrices. Such chiral quantum walks have found applications in routing on quantum networks where directionality is important. It is an open question to construct families of graphs with one-way perfect state transfer. Most examples known in the literature exhibit periodic (or perfect return) property (whose proof requires deep results from number theory).

We assume no background in quantum theory but require mathematical maturity and strong background in linear algebra and analysis. Prior experience with LaTeX and Sage will be useful.

Supervisor: Prof. Pavlos Motakis, York University
Co-Supervisor: Prof. Paul Skoufranis, York University

Project Overview

The purpose of the project to study the intertwining of the analytic and algebraic properties of matrices and geometric objects associated to them. The objective is to formulate specific quantitative conditions and compute theoretical margins of error; if a matrix A satisfies these conditions then it must also satisfy a desired conclusion, within the predicted error. One such problem under consideration will be given an N-dimension matrix A to predict how well it can preserve n-dimensional information by studying its diagonal entries. A second problem concerns studying matrices B that are close to a k-simplex whose vertices lie in the unitary orbit of a self-adjoint matrix A with eigenvalues in [0,1]. In a later stage these discoveries will be put to the test as follows. If we demand that the same conditions are satisfied by a matrix that varies continuously over time can we then continuously track the previously predicted conclusions? The participating students will be exposed to the process of mathematical research through formulating questions, proving theorems, and communicating their results via presentations and articles.

Detailed Description

Rationale

The specific problems under consideration are inspired by operator theory and the theory of operator algebras, both of which are subfields of functional analysis. By stating analogous problems in a more tractable language the participants will be exposed to mathematical research in these areas in a more familiar environment.

Objective

The objective is to compute quantitative estimates related to two problems from matrix theory and their continuous counterparts.

Problem 1

The norm ||A|| of an mxn matrix A is the maximum of |< Ax,y>| over all unit vectors x and y of appropriate dimensions.
An NxN matrix A is said to be a C-factor of an nxn matrix B if there exist matrices L and R of appropriate dimensions so that B = LAR and ||L||*||R|| is at most C.
Given an NxN matrix A of norm one, a positive integer n, and a constant C we study necessary conditions to place on A so that if achieved then A is a C-factor of all nxn matrices B of norm one.

Problem 2

An NxN self-adjoint matrix with eigenvalues in the interval [0,1] is called a positive contraction.
An NxN matrix B that represents A relative to some orthonormal basis is said to be in the unitary orbit of A.
For every positive integer k we study the matrices that are inside and close to a k-simplex whose vertices lie in the unitary orbit of a fixed positive contraction A.
Each of these problems can be enhanced by replacing the given stationary matrix A by a matrix function A=A(t) that varies continuously over time. In Problem 1 we then study conditions so that A(t) is a continuous C-factor of all nxn matrix functions of norm one. In Problem 2 we study k-simplices that continuously deform over time and continuous matrix functions that stay within a certain distance of the deforming simplex.

Tasks, Student Responsibilities, and Timeline

Throughout the project the participants will meet with supervisors twice a week. Furthermore, students are expected to hold independent meetings an additional two times per week. Each member will be asked to make contributions to all aspects of the project. They will be expected to spend time presenting their ideas on how to solve a given problem, to give a brief overview of the project so far, and to prepare written materials.
In weeks 1 to 3 the participating students will be guided through recalling and combining knowledge from linear algebra, analysis, combinatorics, and probability theory. In weeks 4-7 they will be asked to formulate and prove simplified partial statements and discuss possible improvements and ways to prove them. Step by step they will be guided towards asking the right questions and developing answers that may lead to gradual improvements. In the final 2 weeks of the project they will be tasked with preparing a slide presentation and poster that summarizes the conducted research and its conclusions as well as with preparing a short article.

Outcomes

The participating students will develop skills in cooperation, presentation, and independent thought. They will gain confidence and obtain leadership skills through taking on various roles that they might otherwise hesitate to take up voluntarily. Most importantly, they will be exposed to the process of pure mathematical research. They will learn that if the path to a final goal is not apparent then it is useful to formulate and solve a simpler problem and subsequently ask the right questions and develop answers that will yield gradual improvements.