Tuesday, November 22nd, 7pm, Ryerson 352
Tuesday, November 15th, 7pm, Ryerson 352
On the Visibility of Invisible Sets
Tuesday, November 8th, 7pm, Ryerson 352
A planar set A is called invisible, if its
orthogonal projection is of measure 0 in almost every
direction; A is visible, if it is not invisible.
We say that A is invisible from a point, if almost all lines
through that point do not hit the set.
We characterise the sets of the plane from which an invisible set is visible.
Topological invariance of non-topological invariants
Tuesday, November 1st, 7pm, Ryerson 352
Abstract: In this talk I will explain three amazing theorems in geometry/topology, and how they relate to each other. These theorems helped form the current landscape in algebraic topology, differential topology, and differential geometry.
Tuesday, October 25th, 7pm, Ryerson 352
Alphabet Soup: How to Encode Information and Exploit Algebraic Structure
Wednesday, October 19th, 7pm, Eckhart 133
Let's play a game. Suppose we have n people in a room, and each person is given a white or black hat assigned uniformly at random and independently from all other assignments. Each person can see every hat besides his/her own. Each player has an opportunity to either guess the colour of his/her hat, or to abstain from guessing. In order to win the game, each player who guesses must guess correctly, and at least one player must guess. That is, the game is lost if a single person guesses incorrectly, or if everyone abstains. The players may communicate before the hats are handed out, but not afterwards.
It is trivial to come up with a strategy that wins this game with probability 1/2: simply have one player guess his/her hat colour, and have everyone else abstain. And, naively, we are inclined to believe that this winning probability is optimal -- having more than one person guess can't possibly increase the probability of winning this game. But, it turns out, if we're smart about it, that's not the case! We'll introduce error-correcting codes and show how to use coding theory to solve this problem.
This talk will have five parts:
1. We will solve the above problem combinatorially for \(n = 3\), and show that we can win with probability \(3/4\). Prerequisites: showing up to the lecture
2. We introduce the Hamming model for error-correcting codes, explain the significance of their applications, and prove some combinatorial bounds on error correction capacity versus size of code. Prerequisites: binomial coefficients
3. We introduce the families of Hamming codes and linear codes (defining codes by linear transformations), and explain how we can use Hamming codes to win our hat game with high probability for arbitrary n. Prerequisites: linear algebra
4. We introduce cyclic codes, specifically Reed-Solomon and Bose-Chaudhuri-Hocquenghem codes, and explain their relationships to ideals in Galois fields. Prerequisites: Galois theory
5. We introduce the list-decoding model, explain the significance of algebraic structure in decoding algorithms, and show how to efficiently reverse-engineer codeword polynomials and error polynomials from received data by viewing the polynomial coefficients as variables defining systems of quadratic equations. We then exploit finite field structure to linearize these equations so that such coefficients can be solved for using Gaussian elimination. Once we have done this we can isolate the error and codeword polynomials by polynomial long division. This process, in total, takes \(O(n^3)\) time and \(O(q*n*log(n))\) memory, where n is the length of a codeword and q is the size of the code alphabet. Prerequisites: Algorithms, linear programming
Ultrafilters, Ramsey's Theorem, and Logic
Wednesday, October 12th, 7pm, Eckhart 133
How to count with Calculus
Tuesday, October 4th, 7pm, Ry352
Abstract: Counting is hard, but calculus is easy! For example, it takes some thought to see that the non-similar binary trees of fixed length are counted by the Catalan numbers, but any freshman walking the halls of Eckhart can tell you that the derivative of \(x^n\) is \(nx^(n-1)\).
In this talk we will tell you how to show the first statement from the second: how to turn hard counting problems into easy calculus ones. Other examples of problems we'll solve are:
1. N students throw their hats up at graduation. What's the chance that nobody gets their own hat back when they land? By multiplying two Taylor series, we'll find an explicit formula that goes to 1⁄e as N→infinity!
2. It turns out that the Fibonacci numbers are given by the explicit formula $$F_n = (g^n + 1/g^n)/\sqrt(5)$$ where g is the golden ratio. We'll show this by partial fraction decomposition.
3. A drunk man starts at the bar, and stumbles back and forth randomly. On a line and a plane, he will surely return to the bar - but in 3-dimensional space and any higher dimension, this fails to be true! What is even more remarkable is that the solution involves essentially no combinatorics, and is solved by estimating how big a certain integral is.