For other semesters, see the archive here.
12 March 2014
Totally Positive Matrices
A matrix of real numbers is called totally positive if all of its minors (determinants of square submatrices) are positive real numbers. In this talk, we will focus on two problems: parametrizing totally positive matrices, and testing a matrix for total positivity. First, we will give a parametrization of all totally positive matrices in terms of weights of paths on a certain class of graphs; in doing so, we will prove a result known as Lindström's Lemma. Second, we will show that for an n-by-n matrix M, there exist sets S of n^2 minors whose positivity implies the positivity of all (exponentially many) minors of M. We will also describe a large family of such sets S using a combinatorial gadget called a double wiring diagram.
20 March 2014
Existence Theory in Calculus of Variations
The direct method in calculus of variations, developed in the early 20th century, can be used to prove the existence of minimizers to a wide variety of variational problems. In this talk, we will explore the relationship between convexity and lower semi-continuity, an important ingredient in the direct method. We will then be able to use the direct method to establish the existence of weak solutions to the Dirichlet problem in n-dimensions. If time permits, we will also look at some geometric variational problems.
2 April 2014
Gröbner Bases and Computational Algebraic Techniques
Computational algebraic geometry, the study of zeroes of polynomial equations (from a computational perspective), has in recent years seen a rich variety of applications in computer science and optimization. In this talk, we will survey some basic results from computational algebraic geometry: topics will include resultants/discriminants, parametric polynomial equations, and Gröbner bases, the last of which proves Hilbert basis theorem over fields and provides a generalization of the division algorithm for multivariable polynomials. If time permits, applications to optimization and computer science will be discussed.
17 April 2014
Variations on the Polya urn process
The Polya urn process is a famous statistical model demonstrating a phenomenon known as "the rich get richer." Its simplest form works as follows: start with an urn containing b blue balls and r red balls. Every second, select a ball from the urn uniformly at random, and put it back in to the urn along with another ball of the same color. In this talk, we'll analyze a few variants of the Polya urn process using tools from a wide variety of areas of mathematics.
24 April 2014
Bandits and Related Problems
Consider a set of weighted coins with unknown weights. You are allowed N flips in total, with the goal of maximizing the number of heads. Flipping a coin gives you some information about its weight; the challenge is balancing between exploration (flipping a coin to better estimate its weight) and exploitation (flipping the coin you think has the highest weight). This is the simplest version of the multi armed bandits problem, for which several approximate and exact solutions exist. In practice, many problems of interest can be cast in terms of bandits, from clinical trials in medicine (you want to test new treatments, but untested treatments might be harmful) to playing games such as chess and Go (which sequences of moves should be explored?).
30 April 2014
Sieve Theory and the Weak Twin Prime Conjecture
The twin prime conjecture and the Goldbach conjecture are two of the most well-known unsolved problems in number theory. The proofs of almost all the known weak versions of these two conjectures come from sieve theory. In this talk, we are going to talk about the basics of sieve theory, starting with the usual sieve of Eratosthenes. We will try to motivate why sieve methods are natural ways to solve twin prime-type and Goldbach-type problems (but do not quite solve the problem exactly). If time permits, we will talk about the essence of the recent GPY method, which forms the foundation of the recent proof of the weak twin prime conjecture by Yitang Zhang, and the subsequent improvement by Maynard, Tao and a polymath project.
7 May 2014
Getting the most out of your random bits
Sometimes we can use randomness to solve algorithmic problems, if we are allowed to tolerate some small error probability. Often, we would like to avoid using randomness, if possible, but sometimes we will just settle for using not that much randomness. We will show how, given a randomized algorithm, how we can substantially improve on the failure rate without requiring many additional random bits. To do this, we will use some graph theory and linear algebra and sketch the proof given by Impagliazzo and Zuckerman in 1989.
15 May 2014
As the semester draws to a close, many math majors are preparing to head to tropical locations this summer, e.g. Wall Street, Silicon Valley, and Minnesota. Fittingly, we'll be finishing the year with an introduction to tropical geometry, a relatively young field that draws its inspiration from algebraic geometry. The so-called "tropical semi-ring" consists of the real numbers along with an "infinity" element, where the sum of two reals is declared to be their minimum, and the product is declared to be their usual sum: for example, 3+7=3, 3*7=10, (-1)+infinity=(-1), and (-1)*infinity=infinity. In algebraic geometry, one studies solutions to systems of polynomial equations, and the same can be done in this tropical setting. Perhaps surprisingly, while the methods from algebraic geometry do not carry over in any obvious way to tropical geometry, many results and ideas from classical geometry have tropical analogues with a distinctly combinatorial flavor. In this talk, we will explore some of these connections. No prior exposure to algebraic geometry will be assumed.