Archived Talks

Summaries of past talks are available. They are listed here in reverse chronological order. You can also browse past talks by subject through the tags page.

Expander Graphs

Delivered by Frieda Rong on Wednesday November 29, 2017

In this talk, we’ll study graphs which are “sparse” yet “highly connected”. Known as expanders, these graphs exhibit interesting properties which can be viewed from a rich array of analytic, combinatorial, and probabilistic perspectives. Contributions of expanders range from the proof of important results in complexity theory to derandomization of algorithms to the construction of robust networks and cryptographic hash functions. We’ll see one application to coding theory, where expanders can be used to provide asymptotically “good” error-correcting codes with linear time encoding and decoding.

Prerequisites: linear algebra (familiarity with eigenvalues and eigenvectors).

Social Choice Functions

Delivered by Sidhant Saraogi on Wednesday November 8, 2017

Social choice functions help aggregate the opinions of many agents. Social choice problems arise in examples as varied as citizens voting in an election, committees deciding on alternatives, and independent computational agents making collective decisions. We aim to study social choice theory through the lens of boolean functions, and study concepts such as influence and noise stability, which provide analogues for natural concepts in the study of social choice. We will finish off by looking at the famous Arrow’s Theorem often popularly stated as “the only voting method that isn't flawed is a dictatorship”.

Constructive analysis

Delivered by Fengyang Wang on Wednesday November 1, 2017

Constructive mathematics, as the name would suggest, is centered on the philosophy that mathematical proofs should be able to be turned into algorithms. We will contextualize constructive approaches to analysis, roughly following Bridges and Vîţă. This talk has no formal prerequisites beyond an elementary understanding of the real numbers and the usual concept of completeness. In particular, no logical background is assumed; intuitionistic logic will be overviewed in the talk. We will finish with a discussion of the ramifications of completeness of the real numbers.

A summary of this talk is available here.

Automatic sequences

Delivered by Laindon Burnett on Wednesday October 25, 2017

This talk will begin with a brief overview behind the theory of words in mathematics as well as the theory of finite automata in theoretical computer science. After this, we will define what an automatic sequence is, prove some fundamental theorems about them, and investigate some of their more intriguing properties. The majority of information presented comes from the text “Automatic Sequences: Theory, Applications, Generalisations” by Jean-Paul Allouche and the University of Waterloo's own Jeffrey Shallit, from the department of Computer Science.

The speaker has provided a PDF document covering the same content as this talk.

A 3/2-approximation algorithm for the stable marriage problem with ties

Delivered by Felix Bauckholt on Wednesday October 4, 2017

I will introduce the Stable Marriage Problem, and its NP-complete cousin, the Stable Marriage Problem with ties. I will present a simplified version of Király’s 3/2-approximation algorithm, which archieves the best approximation ratio known.

The slides for this presentation are available.

Markov Chain Monte Carlo

Delivered by Jacob Jackson on Wednesday October 4, 2017

The talk will introduce Markov chain Monte Carlo methods as a means of sampling from a distribution. The Metropolis-Hastings algorithm will be discussed as well as applications of Markov chain Monte Carlo for Bayesian inference and optimization.

Will expect familiarity with basic probability theory, especially conditional probability.

The slides for this talk are available at Jacob Jackson’s website.

Cantor Set and Dynamical Systems

Delivered by James Bai on Friday March 31, 2017

The talk will be begin on the cosnstruction of the most commonly used tenary Cantor set. The talk will then talk about the common properties of Cantor set and methods of evaluating the size of the set. Then, depending on time, a brief introduction will be given on the dynamical system and chaos.

A summary of this talk is available here.

Group Theoretic Attacks on the Enigma Cipher

Delivered by Laindon Burnett on Friday March 31, 2017

Metric embeddings and dimensionality reduction

Delivered by Frieda Rong on Friday March 31, 2017

In this talk, we consider embeddings which preserve the pairwise distances of a set of points. It is often useful to find mappings from one high dimensional space to a lower dimensional space that preserve the geometry of the points. One source of applications is in streaming large amounts of data, for which storage is costly and/or impractical. However, the study of such embeddings has also inspired developments in the design of approximation algorithms and compressed sensing.

At the crux of the talk is the remarkable Johnson-Lindenstrauss lemma. This fundamental result shows that for Euclidean spaces, it is possible to achieve significant dimensionality reduction of a set of points while approximately preserving the pairwise distances. An elementary proof will be given, along with subsequent speed improvements with sparse projections and an interesting use of the Fourier transform. We will also discuss applications of the lemma to the fields mentioned above.

Lie Groups and Special Relativity

Delivered by Mohamed El Mandouh on Friday March 24, 2017

Brachistochrone

Delivered by Manas Joshi on Friday March 24, 2017

In the late 1600’s, Johann Bernoulli came out with a problem to challenge the world’s greatest mathematicians. The problem, known as the Brachistochrone, had garnered some interest and eventually was solved by Johann, Jacob Bernoulli and Newton amongst others. In this talk, we will analyze the solution given by Leonard Euler (and Lagrange), which started a new field of Calculus, called the Calculus of Variations. We will prove the most fundamental equation, Euler-Lagrange, and see how this can be applied to solve the Brachistochrone problem.

Universal Property of Quotients

Delivered by Lirong Yang on Friday March 17, 2017

In this talk, we generalize universal property of quotients (UPQ) into arbitrary categories. UPQs in algebra and topology and an introduction to categories will be given before the abstraction. As in the discovery of any universal properties, the existence of quotients in the category of sets and that of groups will be presented.

If you have not yet been exposed to group theory, please read Monoids and Groups for an introduction.

A summary of this talk is available here.

Inverse Galois Theory

Delivered by David Liu on Friday March 17, 2017

Almost 200 years after Évariste Galois's death, there is still one question about Galois groups — the symmetries of the roots of polynomials, that still remains unsolved. This is the Inverse Galois Problem — whether every group is a Galois group of a Galois extension of the rational numbers. In this talk, I will give an overview of the progress that has been made, the approaches that mathematicians are making, and directions for further research.

A note on the requirements for this talk: It is recommended that you be comfortable with groups, fields, field extensions, automorphisms, and basic Galois theory. This requirement can be met by any of the following suggested alternatives:

A prerequisite knowledge presentation about Galois theory will be given at 17:00, prior to the beginning of the talk at 17:30. This presentation will last about 20 minutes. If you are unfamiliar with the material, it is recommended that you read some of the linked material above in addition to attending this presentation. Attending this presentation is optional. The reference material used for this presentation is the Galois Theory document.

Bloom Filters and Other Probabilistic Data Structures

Delivered by Luthfi Mawarid on Friday March 3, 2017

With the advent of big data, the ability to process large volumes of data is becoming increasingly important. For instance, when dealing with large data sets, we may want to perform simple operations such as counting the number of unique elements or checking whether or not an element is present in the set. While there are deterministic data structures, such as hash tables, that can perform these quickly, the sheer size of the data involved makes their use largely impractical and unscalable.Instead, we may want to trade-off some accuracy in our answers in exchange for greater space efficiency and ease of parallelization. For this, we introduce the concept of probabilistic data structures.

In this talk, we will mainly focus on Bloom filters, which are commonly used to test set membership and speed up data access. We will explore its main use cases, its implementation details, and the mathematics behind it. If time permits, I will also talk about the count min-sketch, used for frequency counting, and/or the HyperLogLog counter, used for cardinality estimation.

This talk will assume basic knowledge of probability.

Total Functional Programming

Delivered by Adam Hofmann on Friday March 3, 2017

Total functional programming is a paradigm of functional programming with the additional restriction that all functions must be total; that is, every function is defined for every element of its domain.

The immediate benefits of total functional programming are clear; every function in a total language is guaranteed to terminate and not cause a runtime error. This talk will cover the basics of writing and understanding functions that are total, as well as benefits that come from having totality.

Also in the scope of this talk is the major trade offs of total functional programming, including Turing completeness and things like input and output that seem unattainable. This is accompanied by strategies to write functions with non-trivial proofs of termination such that totality is guaranteed and verifiable by the interpreter.

General Secure Multi-Party Computation from any Linear Secret-Sharing Scheme

Delivered by Zihao Zhu on Friday February 17, 2017

As more and more sensitive data gets digitized, there is a need to ensure privacy and reliability of the data, especially in the face of adversarial parties who attempt to corrupt or unwanted access to sensitive secrets.

In many instances such as online gambling, bidding, and even Google's targeted advertisements, a client wants to be able to take inputs from multiple sources (for example, auction bids) and produce an output (for example, the highest bidder) without revealing any information about the other inputs. We will use such scenarios as well as more cryptography related ones in order to motivate Multi-Party Computation as a method to compute on encrypted data. With MPC, we will quickly see it's limitations with unsecure channels and first develop secret sharing schemes (specifically linear secret sharing schemes) such as Shamir's scheme, and soon after, verifiable secret sharing schemes.

We will introduce the different types of adversarial structures and explore both the robustness and limitations of secret sharing schemes against them.

Finally, we will show that all Linear Secret Sharing Schemes can be constructed to be verifiable. We will explore the consequences of this and discuss techniques in their construction.

Prereqs: Math136 used in proofs

A summary of this talk is available here.

Bitcoin and the Blockchain

Delivered by Ben Zhang on Friday February 17, 2017

In this talk, we will learn about the principles behind the Double Spend Problem, the Blockchain, and explore the various ways this technology is being used today.

Transferring money in the physical world is easy. However, the transfer of virtual currency is not as easy to validate. The Double Spend Problem has long stood in the way of a free (libre et gratis) virtual currency, and the world found a need for a third party (usually in the form of large banks) to validate all virtual transactions.

In 2008, a mysterious individual known as Satoshi Nakamoto published a paper titled "Bitcoin: A Peer-to-Peer Electronic Cash System" which describes a system for virtual transactions to be validated through the distributed computing power of the community. The system, known as the Blockchain, uses hashing and non-deterministic mathematics to protect itself from Double Spending attacks. Nakamoto's paper led to the creation of free online currencies such Bitcoin, Litecoin, and Ethereum, which are used in marketplaces today.

Prerequisite Information: Middle school math.

Quantum Computing

Delivered by Michael Pang on Friday February 10, 2017

Introduction to quantum computing. We start off by tackling a classical problem via deterministic and probabilistic computation and then motivate a quantum model of computation. Along the way we lay out some of the mathematics needed to describe quantum computation and how it corresponds to key concepts in quantum mechanics such as interference and superposition.

Ordinals

Delivered by Eddie Onochie on Friday February 10, 2017

In this talk we will talk about ordinals and the philosophy of infinity. We will define what ordinals are and how to construct them. We will also define transfinite recursion and use the axiom of choice to give meaning to the "cardinality" of a set.

A summary of this talk is available here.

$p$-adic Numbers

Delivered by Akshay Tiwary on Friday February 3, 2017

In this talk we will discover an alternate way to define the "size" of a ration al number. We will define the p-adic absolute value and see that this absolute value is Non-archimedean and that this fact leads to a a geometry that is very different from the geometry of the Real numbers (every p-adic triangle is isosc eles!). In addition I will show you some fun ideas from p-adic numbers (which I will denote by $\mathbb{Q}_p$ like the fact that $\sum_{n = 1}^{\infty} 3^n$ converges and how every element of $\mathbb{Q}_p$ has a base $p$ expansion. This is meant to be a very leisurely talk with almost no prerequisites and it should be fun so please come for it!

$q$-analogs

Delivered by Fengyang Wang on Friday February 3, 2017

Some of the most interesting results in combinatorics are generalizations of simple problems or theorems to problems or theorems parameterized by a parameter $q$ (often complex-valued). By taking the limit as $q\to1$, the simple problems can be recovered. Surprisingly, many of these $q$-analogs take similar forms, and are seen across a wide variety of problems that may initially seem unrelated.

Concepts from MATH 239 will be used. It is heavily recommended that people who have not taken MATH 239 or an equivalent course read some material on ordinary generating functions.

A summary of this talk is available here.

Tensor Products

Delivered by Felix Bauckholt on Friday January 27, 2017

What is a tensor product? How are they useful? This talk will elaborate on this broad, widely applicable topic.

Integrability of Riccati Equations

Delivered by Letian Chen on Friday January 27, 2017

In 1841, 3 years before Joseph Liouville discovered transcendental numbers, Joseph Liouville showed that the Riccati equation $y' = ay^2 + bx^m$ has a quadrature solution if and only if $m = 0, -2, -\frac{4n}{2n±1}$. Nowadays, we see Liouville's results as the foundation to qualitative analysis to differential equations, a fascinating subarea of DEs, which studies for example the existence and uniqueness of different kinds of equations. In my talk, I will (hopefully) prove the classical result of Liouville after a quick review of history and related linear theory.

Diophantine Approximation and the Discovery of Transcendental Numbers

Delivered by Anton Mosunov on Friday January 20, 2017

In 1844, Joseph Liouville discovered transcendental numbers — those numbers that are not roots of polynomials with rational coefficients. Nowadays, we see Liouville’s discovery as the foundation of Diophantine approximation, a fascinating subarea of number theory, which studies how well algebraic numbers can be approximated by the rationals. In my talk, I will prove the classical result of Liouville and explain further advances in the area, such as Thue’s theorem and the celebrated theorem of Roth, which enabled its discoverer to receive the Fields medal in 1958.

Game Theory (Part 2): Extensive Form Finite and Infinite Games

Delivered by Koosha Totonchi on Friday January 20, 2017

An extensive form game, unlike a regular one-shot-game, has the element of sequential or repeated movement. Chess for example, is an extensive form game. However, we will see that our mathematical definition of “game” will be much broader, so models we construct can be applied to problems in economics, computer science, and engineering—not just chess.

We will explore what it means to “solve” a game where players make back to back moves. We will also go over games where players pick their moves at the same time but play over and over. There will be a review of basic definitions from Game Theory Part 1, and we will introduce some new terms which will help us with extensive forms.

At the end, we can hopefully look at some interesting applications.

Note: this builds on the first Game Theory talk given in Fall 2016. If you need to review important concepts or you couldn’t attend, a webpage with definitions and basic information is available here. We’ll do a brief review so don’t worry too much! If you didn’t come to the first session, you should be able to understand everything here regardless.

Voting with Homomorphic Encryption

Delivered by Sidhant Saraogi on Friday December 2, 2016

In light of the recently concluded Elections or as John Oliver would call it “A horifying glimpse at Satan's Pinterest Board 2016”, “The One who must not be named” has repeatedly insinuated that the elections have been rigged. Our humble aim, present a voting scheme where:

We delve into two areas on our way to prove our goal :

We might also, if time permit, talk about more modern systems of enabling fair elections that have even been implemented in real life.

This talk is based off Ron Rivest’s lecture, of which a summary is available.

How to Complicate Fourier Analysis

Delivered by Mohamed El Mandouh on Friday December 2, 2016

Fourier analysis was initially introduced as a way to study the thermodynamic heat equation. At its simplest, it is the study of how to represent functions as an infinite sum of sines and cosines. However, the evil mathematicians felt that Fourier analysis was too simple and decided to steal it from the hardworking physicists and expand on it. In addition, they decided to complicate it by introducing Harmonic analysis. So, what is the difference between Harmonic and Fourier analysis? We say that Harmonic analysis is the process of representing functions on a locally compact group G as a sum of the characters of the group, and Fourier analysis restricts this process to abelian groups.

In this talk I will introduce the Fourier series, the Fourier transform and how it applies to abelian groups. What about non-abelian groups, you might ask? The answer is Harmonic analysis! Finally, I will explain the role of Fourier transform in quantum mechanics, specifically how the Fourier transform interchanges position and momentum space.

Quandles: The Algebra of Knots

Delivered by Brennen Creighton-Young on Friday November 25, 2016

One of the major goals of knot theory is to determine whether or knot two knots can be continuously deformed into one another. This idea can be fully captured algebraically — and leads us to algebraic structures that not only capture the desired notion of knot deformations, but reveal themselves as truly fascinating mathematical objects. We will use only linear algebra and elementary abstract algebra.

Though continuous deformation is a straight forward idea, the rigorous definition of this, the notion of ambient isotopy, is practically unusable. This talk will provide a quick overview of basic knot theory and will work towards developing numerous algebraic strategies to identify when two knots are ambient isotopic. We will focus mostly on providing motivation for keis, an algebraic representation of knots, as well as their generalization, quandles. Quandles will prove to be not only helpful with respect to the goal of the classification of knots, but also as rich algebraic structures. The talk will involve small amounts of group theory, linear algebra and module theory.

Naïve Lie Theory

Delivered by Aidan Patterson on Friday November 25, 2016

In 1870, Sophus Lie was studying the symmetries of differential equations, which generally form “continuous” groups. The analogous problem for polynomials was solved by Galois previously, so there was incentive to solve the related problem for these new kinds of groups. We’ll motivate such continuous groups by looking at matrices, assuming only a little linear algebra.

Lie started a study of simplicity in these continuous groups. Lie understood these groups as groups generated by infinitesimal elements, which led him to believe that a group $G$ should be generalised to consider infinitesimal elements.

Today we separate the infinitesimal elements of a group $G$ to form a Lie algebra $g$, which captures most of the important structures of $G$, but is easier to handle. This talk will focus on motivating Lie's definitions, and provide some techniques used to prove simplicity for Lie groups. As well, some specific examples such as $\mathrm{O}(n)$, $\mathrm{SO}(n)$, $\mathrm{U}(n)$, $\mathrm{SU}(n)$, and $\mathrm{Sp}(n)$ will be mentioned to illustrate the concepts presented.

Please read this basic overview of Lie Theory.

Basic Elliptic Curves

Delivered by Akshay Tiwary on Friday November 18, 2016

Elliptic Curves lie in the intersection of Algebra, Geometry, Number Theory and Complex Analysis. While my talk won't require any experience with complex analysis or algebraic geometry, I hope to expose you to this active area of research. Although I could tell you that the meat of Wiles' proof of Fermat's Last Theorem involved proving a special case conjecture previously known as the Taniyama Shimura conjecture involving elliptic curves, or that the Birch and Swinnerton-Dyer conjecture is an open millenium prize problem that talks about the relation between the arithmetic behaviour of elliptic curves and the analytic behaviour of an L-function, or that elliptic curves over finite fields is so useful for cryptography that there was a memo that recommended elliptic curves for federal government use in 1999, I don't have to because you're a math student who will attend this talk without needing to be wowed with cool applications, right?

Hypercomplex Numbers

Delivered by Fengyang Wang on Friday November 18, 2016

There are exactly three distinct two-dimensional unital algebras over the reals, up to isomorphism. Each of these algebras corresponds to a unique geometry, with applications. This talk will develop the concepts needed to understand two-dimensional algebras over the reals, starting from the definitions of key concepts. We will rediscover the familiar complex numbers and generalize its construction to find the other hypercomplex number systems. We will then prove the result that these are the unique hypercomplex number systems, up to isomorphism. Finally, we will discuss possible generalizations to $n$ dimensions. Please ensure that you have a good understanding of fundamental concepts of two-dimensional linear algebra.

We will use Catoni, F., Cannata, R., Catoni, V., & Zampetti, P. (2004) as a reference.

A summary of this talk is available here.

Random Graphs and Complex Networks

Delivered by Frieda Rong on Friday November 11, 2016

From the graph of Facebook friendships to the neurons inside your brain, networks are all around us. We’ll go over some surprising connections in network theory and see some of the following:

Simplicial Homology

Delivered by Kai Rüsch on Friday November 11, 2016

How do we count how many holes a shape has? We can answer this question using homology groups, whose order's count the number of $n$-dimensional holes.

A summary of this talk is available here.

Game Theory (Part 1)

Delivered by Koosha Totonchi on Friday November 4, 2016

A game is a “mathematical model between interacting decision makers” where each player must make choices based on a set of rules. Every individual in a game must also have a preferred reaction to any combination of actions taken by other agents. Game theory is about the study and application of these models. It involves various solution concepts and methods that can be employed to predict the outcomes of strategic engagements. This talk will introduce the major ideas in the field. There will be a focus on basic definitions, types of games, and how we can “solve games” using the Nash equilibrium. Hopefully we’ll get to “play” some ourselves. Towards the end, we can also review some neat unsolved problems in game theory that are very easy to understand, but prove really difficult to solve.

A summary of this talk is available here.

Integration

Delivered by Gregory Patchell on Friday October 28, 2016

The first part of this talk will be concerned with a brief introduction to measure theory. We will answer questions such a: How do we measure sets? Can every set be measured?

The second part of this talk will be the construction of the Lebesgue integral along with basic properties of the Lebesgue integral, along with comparisons to Riemann integration as we go. From Math 148, we saw that pointwise convergence doesn’t play well with Riemann integration. We will see that with the powerful Monotone Convergence Theorem and the Dominated Convergence Theorem, pointwise convergence and Lebesgue integration are a match made in heaven.

Outline

Convex Optimization

Delivered by Rolina Wu on Friday October 28, 2016

This talk will introduce the basics for Convex Optimization, several popular optimization algorithms, and the application for convex optimization in Machine Learning.

Boyd and Vandenberghe, 2004 will be used for reference.

Reinforcement Learning in Games

Delivered by Agastya Kalra on Friday October 21, 2016

Category Theory

Delivered by Luthfi Mawarid on Friday October 21, 2016

This talk will cover the very basics of Category Theory, motivated by simple examples using the category of sets. I will then introduce some applications to other areas of mathematics, such as linear algebra and programming language theory.

Types and Object-Oriented Programming

Delivered by Nikita Kapustin on Friday October 14, 2016

I'll be talking about how to use basic types like sets and functions to construct other types and use them to represent objects.

Information Theory

Delivered by Sidhant Saraogi on Friday October 14, 2016

I will try to provide a brief introduction to Information Theory working towards motivating Shannon's Source Coding Theorem. We will use rather simple examples (for e.g. Repetition Codes) to explain the idea of noisy channels and similarly simple examples to explain the idea behind the theorem and eventually try to prove it for a rather specific example. (if we have the time !)

Infinitely Awesome Graphs

Delivered by Zouhaier Ferchiou on Wednesday October 12, 2016

This talk will cover the basics of dealing with graphs with an infinite number of verticies, focusing mostly on countably many verticies.

I will cover basic definitions of graph theory, Menger's theorem (Only 1 version, don't worry), trees, girths and chromatic numbers briefly for people not familiar with the terms. We will then jump into the sweet stuff, defining teeth and spines, local infinity, rays...

I will then present (and prove some) quite useful theorems and lemmas, including <q>de Bruijn & Erdos theorem</q> and <q>Star-Comb Lemma</q>. Finally, we will talk about Universal graphs, the Rado graph and why they are cool.

Ultrafilters

Delivered by Felix Bauckholt on Wednesday October 12, 2016

In this talk, I will try to explain what ultrafilters are. I will do this by presenting a few motivating examples, and also some examples that, even if they don't motivate anything, are just really cool.

Hyperreal numbers are used to motivate this talk.

Groups

Delivered by Fengyang Wang on Wednesday October 12, 2016

This talk will cover the basics of group theory. There are no official prerequisites for this talk, but MATH 145 and MATH 146 are an asset. The group theory part of the talk will mostly be based on Alekseev, 2004, specifically sections 1.1 (motivation), 1.2 (transformation groups), 1.5, 1.9, and 1.13 (various morphisms), and 1.11 (quotient groups).

Due to time constraints, it is inevitable that some content must be rushed. I will not go over proofs and derivations in full rigour, and I highly advise studying the reference material after the talk to catch up on what you may have missed. Please message me in advance if there are any other subjects in particular that you would like me to discuss.

A summary of this talk is available here.