Mathematics Department

Colloquium

Upcoming Seminar

April 24, 4:10 PM in Physics 123
Noncommutative Fourier analysis of partially ranked data
Luis David Garcia, Department of Mathematics and Statistics, Sam Houston State University

Suppose that you are given the result of a survey in which participants are asked to identify their top \(k\) choices out of \(n\) items, e.g., the preferred 3 types of cookies out of 6 Girl Scout cookies. There are several natural summaries of the number counts in this data. For example, we could consider the total number of voters approving of each different \(k\)-subset of the \(n\) candidates. We could also count the number of voters approving of each individual candidate, or the number of voters approving of each different pair of candidates, or more generally the number of voters approving of each different \(i\)-subset of the \(n\) candidates. This gives rise to a nested collection of summary statistics that could be used to describe the result of this survey. A natural question to ask is which of these summary statistics best describe the result of our survey? Which statistics capture all the “juice" in the data? About two decades ago, Persi Diaconis proposed using Fourier analysis and algebraic techniques to answer these type of questions for the case of fully ranked data. However, very little is known for the case of partially ranked data. In this talk, we will give an elementary introduction to the Fourier analysis and algebraic techniques involved in the study of both fully and partially ranked data.

Most Thursday afternoons during the academic year, the Reed College Department of Mathematics hosts a math talk. The talks are directed to our mathematics majors but are usually accessible on a variety of levels. Refreshments are served before the talks. For more information, please email davidp at reed.edu.

2013-14 Schedule

Fall

4:10-5:00 in Physics 123 (unless marked otherwise). Directions to Reed.

Sept 5Meeting with majors. No talk this week.
Sept 12Student Presentations
Maddie Brandt, Joseph Rennie, Qiaoyu Yang, and Kuai Yu

Maddie Brandt:  Packings of Four Equal Circles on Flat Tori
Joseph Rennie:  Algorithms for Determining Zero Set Topologies
Qiaoyu Yang and Kuai Yu:  Parking functions and tree inversions

Sept 19Maximally Intransitive Dice
Joe Buhler, CCR/Reed College
It's been known for a long time that there are three dice \(A\), \(B\), \(C\) such that \(A > B > C > A\) where "\(A> B\)" means that \(A\) beats \(B\) in the sense that the probability that a roll of \(A\) is higher than a roll of \(B\) is strictly bigger than 1/2. In fact there are dice such that \(A>B>C>A\) and yet \(A^{[2]}<B^{[2]}<C^{[2]}<A^{[2]}\) where, e.g., \(A^{[2]}\) denotes the sum of two rolls of \(A\). The first goal of this talk is to give a vast generalization of this, and the second is to discuss the refinements of the Central Limit Theorem that are necessary to give a proof of that is, in a certain sense, constructive, e.g., could be used to make and win certain wagers.
Sept 26Making juggling patterns from matrices
Allen Knutson, Department of Mathematics, Cornell University
Given a \(k\times n\) matrix of rank \(k\), when we do Gaussian elimination we can ask where the pivot columns are, and get a \(k\)-element subset of \(\{1,\dots,n\}\). This subset changes in simple ways if we rotate the first column to the end. When juggling \(k\) balls, one throw per second, at any given moment we can ask when the balls will land. This subset of future times changes in simple ways if we make one throw and wait one second. I'll give a mathematical definition of "juggling patterns" and explore this association of patterns to matrices. Much demonstration will ensue. This work is joint with Thomas Lam and David Speyer.
Oct 3Linear spaces of singular matrices
Nathan Ilten, Department of Mathematics, UC Berkeley
The space of singular \(n\times n\) matrices over a field \(K\) may be viewed as the hypersurface of \(K^{n^2}\) on which the \(n \times n\) determinant vanishes. This space has many interesting geometric properties; in particular, it contains many linear subspaces of \(K^{n^2}\). In this talk, I will introduce a geometric object, called a Fano scheme, parametrizing these linear subspaces. We'll look at some basic examples of Fano schemes, and then see a result characterizing exactly when our Fano schemes are connected. This is joint work with Melody Chan.
Oct 10Quaternions and Dirac's belt trick
Kyle Ormsby, Department of Mathematics, MIT (& Reed College)
By studying the geometry of four-dimensional Euclidean space, we'll construct the quaternions, an enhancement of the complex numbers which contains extra square roots of -1. These four-dimensional Platonic ideals cast shadows in our three-dimensional cave: unit length quaternions induce rotations of \(\mathbb{R}^3\). By analyzing this projection, we'll learn something about the topology of rotations, which will in turn explain Dirac's belt trick (a method physicists use to fool people into thinking they understand quantum mechanics). Following an idea of Louis Kauffman, we will put our newfound knowledge to work and create a physical model of my favorite group, the binary tetrahedral group.
Oct 17Introduction to the dark arts: internal set theory and nonstandard analysis.
Jacob Perlman ('09), Department of Mathematics, University of Chicago
Did you know that most things you work with are too big? Simply too big, far too much, and a great deal too many. By introducing some axioms for clearing up the infinite clutter we spend much of our time embroiled in, internal set theory provides a rigorous toolbox of big numbers, small numbers, equalish, and other such vagaries, making many concepts and proofs cleaner and more intuitive; examples will hopefully be persuasive. Sadly there are some costs, mostly in the form of ridiculous sounding consequences; examples will hopefully be controversial and borderline offensive. I will conclude with the technical sense in which objecting to these consequences are harmless. Warning: this talk may contain light doses of formal logic and axiomatic set theory.
Oct 24Fall break
Oct 31Non-Euclidean Pythagorean Theorem and a Problem of Euler.
Robin Hartshorne, Department of Mathematics, UC Berkeley
In Euclidean geometry, the well-known Pythagorean theorem says that the square on the hypotenuse is the sum of the squares on the legs of a right triangle. If one looks for triangles with integer sides, one gets the so-called "Pythagorean triples" such as 3,4,5 and 5,12,13. In non-Euclidean geometry there is a similar problem of finding right triangles with rational numbers for lengths of sides. This is more sophisticated, and turns out to be equivalent to a problem considered by Euler in his Algebra of 1775. I will explain how to find some of the solutions to this problem. Prerequisites: high school geometry and high school algebra.
Nov 8
Please note change in date.
How to Tell When You Know Enough
Chris Haulk ('05), Google

(From wikipedia:) In statistics, sequential analysis or sequential hypothesis testing is statistical analysis where the sample size is not fixed in advance. Instead data are evaluated as they are collected, and further sampling is stopped in accordance with a pre-defined stopping rule as soon as significant results are observed. Thus a conclusion may sometimes be reached at a much earlier stage than would be possible with more classical hypothesis testing or estimation, at consequently lower financial and/or human cost.

I'll give an overview of some key ideas in this subject.

Nov 14Of Elves and Oracles: A Taste of Modern Cryptography
Seth Terashima ('10), Department of Computer Science, Portland State University
Every mathematician knows the importance of getting definitions "right". This is equally true in computer science, and especially true in the field of cryptography, where the stakes tend to be rather high. For example, how do we formally define a "secure" encryption algorithm? And what assumptions are reasonable (and useful) when proving that an algorithm meets the criteria? In this talk, I will draw on joint work with Tom Shrimpton and Will Landecker ('06) to exhibit some of the machinery and proof techniques used in modern cryptography.
Nov 21Partial orientations of graphs and the combinatorial Riemann-Roch theorem
Spencer Backman, School of Mathematics, Georgia Institute of Technology
In 2007 Baker and Norine proved a combinatorial Riemann-Roch theorem for graphs analogous to the classical statement for Riemann surfaces. Their proof employed chip-firing, a deceptively simple game on graphs with connections to various areas of mathematics. There is a story which runs parallel to chip-firing describing certain reorientations of graphs, which was first introduced in the setting of acyclic orientations by Mosesian and later extended to arbitrary orientations by Gioan and Las Vergnas. In this talk, we describe a generalization of Gioan and Las Vergnas's cycle-cocycle reversal system for partial orientations of a graph and explain how this setup allows for a new proof of the Riemann-Roch theorem. Time permitting, we will discuss an interesting connection with the max-flow min-cut theorem from combinatorial optimization.
Nov 28Thanksgiving
Dec 5On counting upper interactions in Dyck paths
Yvan Le Borgne, Simon Fraser University & CNRS/LaBRI (Université Bordeaux)

The Catalan numbers forms the counting sequence of many classes of objects in enumerative combinatorics (see R.P. Stanley Catalan addendum). This sequence frequently results from the existence of a recursive decomposition of objects into one atomic element and two, possibly empty, smaller objects of the same class. In terms of generating functions, this decomposition turns into an algebraic equation of degree two.

A classical interpretation of the Catalan numbers are the Dyck words. A Dyck word of size \(n\) is a word on the alphabet \(\{a,b\}\) which contains \(n\) occurrences of each letter and where each prefix contains at least as many occurrences of letter \(a\) than occurrences of letter \(b\). An upper interaction in a Dyck word is any occurrence of a factor \(b^ka^k\) with \(k\geq 1\). The enumeration of Dyck words according to their size and number of upper interactions creates a correlation between the two subwords of the usual recursive decomposition of Dyck words.

The aim of this talk is to explain various ways to tame this correlation, revisiting some of the classical methods to count Dyck words via a generating function. This will involve the kernel method, solving some \(q\)-algebraic equations, the theory of heaps and some formal regular/algebraic languages.

Based on this and additional recent progress by the speaker.

Spring

4:10-5:00 in Physics 123 (unless marked otherwise). Directions to Reed.

Jan 30
Feb 6Asymptotics of Cyclic Codes
Michael E O'Sullivan, Department of Mathematics & Statistics, San Diego State University
Codes for correcting errors that occur in transmission of data are found in numerous electronic devices. I will describe cyclic codes, which are a broad family of codes that are widely used and have interesting algebraic properties. The focus of the talk will be asymptotics: does there exist a "good" sequence of cyclic codes, one in which the length of the codes goes to infinity while the dimension and minimum distance don't approach zero.
Feb 13No talk this week.
Feb 20Nonnegative polynomials and sums of squares
Greg Smith, Department of Mathematics and Statistics, Queens University
A polynomial with real coefficients is nonnegative if it takes on only nonnegative values. For example, any sum of squares is obviously nonnegative. For a homogenous polynomial, Hilbert famously characterized when the converse statement holds, i.e. when every nonnegative homogeneous polynomial is a sum of squares. After reviewing the history of this problem, we will examine this converse in a new setting. In particular, we will provide new examples in which every nonnegative homogeneous polynomial is a sum of squares. This talk is based on joint work with Grigoriy Blekherman and Mauricio Velasco.
Feb 26
Please note change in date.
Please note change in location.
Derandomization and Polynomial Identity Testing
Matthew Anderson, University of Cambridge
Location: Library 204

Randomness is a powerful computational resource that enables public-key cryptography, a cornerstone of the modern Internet, and powers extremely efficient data structures, like hash tables. In practice, randomness is algorithmically useful: There are many instances of problems that have simple efficient randomized algorithms but yet have no known efficient deterministic algorithm.

Is randomness essential to efficient computation?

In my talk I will survey several problems with natural and efficient randomized algorithms: Sorting, Primality Testing, and Polynomial Identity Testing. The first two problems also have efficient deterministic algorithms. However, an efficient deterministic algorithm for deciding whether a given polynomial identity holds has remained elusive. Indeed, derandomizing the general case of identity testing would imply circuit lower bounds, i.e., imply there is an explicit problem that is impossible for small Boolean circuits to compute, answering a central question in computational complexity theory that has been open for nearly half a century.

Towards answering this question I will discuss some of my work on efficient deterministic identity tests for constant-read multilinear formulas, i.e., arithmetic formulas where each variable occurs only a constant number of times and each subformula computes a multilinear polynomial.

Feb 27Stronger isn't always better
Adam Groce, University of Maryland, College Park
Today, governments, universities, hospitals, and companies all maintain huge databases of private information. That information, if it could be analyzed, holds the key to a remarkable array of potential discoveries in medicine, social science, and other areas. However, the private nature of the data limits much of this analysis. The field of private data analysis seeks to provide tools for analyzing such data without violating privacy. However, before such tools can be created, it is necessary to formally define the desired notion of "privacy." I will survey existing definitions and then introduce a new definition, coupled-worlds privacy, proposed as part of my PhD work. The goal of coupled-worlds privacy is to formally model adversarial uncertainty in an effort to increase the accuracy of private data analysis. I will compare this definition with prior efforts toward the same end and discuss future directions for this definition and for private data analysis in general.
Mar 6The Little Remainder Theorem that Could
Anna Johnston, Raytheon
One theorem has the power to break cryptography, share secrets, correct errors, compute multiplicative inverses in finite fields, and enable countless other information theoretical and mathematical applications. This powerful little theorem is the da yen, commonly called the Chinese remainder theorem. The aim of this talk is to describe one of the least known of these applications: derivation of truncated Taylor series. This derivation gives an alternate perspective on Taylor series as an interpolated polynomial. On the way to this derivation the theory and history of the da yen will be described, including the origins of the names 'da yen' and Chinese remainder theorem.
Mar 13Map making and vice versa
Zack Treisman, Department of Mathematics, Western State Colorado University

This talk is probably not about cartography.

Coordinate systems are descriptions of geometric objects, and there are ambiguities that can appear in these descriptions. I'll discuss one surprising example coming from a situation that we all think we understand, and how this example can help us understand some interesting interactions between algebraic geometry and string theory via motivic integration.

Mar 20Spring break
Mar 27Affine Geometry Inspired by the Game of SET\(^{\circledR}\)
Liz McMahon, Department of Mathematics, Lafayette College
The cards in the game of SET\(^{\circledR}\) are an excellent model for the finite affine geometry \(AG(4,3)\). We will explore how to use the game to visualize the structure of the geometry and to explore that structure. We will focus on complete caps, which correspond to largest possible collections of cards with no sets. There is an interesting structure to these caps, and even more, the geometry can be partitioned into four disjoint complete caps together with a single point closely related to the caps. Recent results make the structure of these partitions even clearer.
Apr 3Pick a tree, any tree
Gary Gordon, Department of Mathematics, Lafayette College
Trees are an extremely important and useful topic in graph theory and network design. I'll talk about some of the motivation and history of the subject, including Cayley's famous formula that counts the number of spanning trees of a complete graph. Then we'll use that formula to figure out the probability that a randomly chosen subtree of a complete graph is a spanning tree. This is joint work with Alex Chin, Kelly MacPhee and Charles Vincent, three undergraduates in Lafayette College's REU program last summer. No prior knowledge of graph theory will be assumed.
Apr 10(I've got) Topological Data Analysis on the Brain
David Romano, Center for Interdisciplinary Brain Sciences Research, Stanford
Topological Data Analysis (TDA) is a recently developed approach to analyzing data, which, rather than extract information from data through the statistical notion of distribution, takes the point of view that the shape of the data itself may encode important information as well. In this talk I will describe an algorithm that has been one of the core tools of TDA, and will show how it has been applied so far in the context of biomedicine.
Apr 15
Please note change in date.
Please note change in location.
Zen and the Art of Debugging
Eric Roberts, Stanford University
Location: Eliot 314
Debugging is an essential skill that computer science students often find difficult to master. In this talk, I will explore the history, philosophy, psychology, and strategies of debugging and offer suggestions to reduce the frustration associated with this challenging—but ultimately rewarding—activity. I will also explain why Robert Pirsig's masterpiece, Zen and the Art of Motorcycle Maintenance, stands as one of the best guides to debugging practice.
Apr 17What's in a polynomial (or power series)? A partial history of the notion of 'content', from 1801 to 2014.
Neil Epstein, Department of Mathematical Sciences, George Mason University
Let \(f\) be a polynomial with coefficients in a commutative ring \(R\). One then defines the content \(c(f)\) of \(f\) to be the ideal of \(R\) generated by the coefficients of \(f\). Is this function \(c\) multiplicative? Sometimes it is; for instance, when \(R\) is the integers. When it isn't multiplicative on the nose, it is multiplicative up to a particular kind of multiple. What happens when one allows power series instead of restricting to polynomials of finite degree? In this case, one must impose some additional finiteness conditions on the ring (namely, Noetheriannness), but the above results still hold, as I had a part in showing earlier this year. One may also generalize these concepts to more general extensions of rings (that is, other than \(R \rightarrow R[X]\) and \(R \rightarrow R[\![X]\!]\)), called content algebras. These developments have taken over two centuries to be established, and have important implications for unique factorization, integrality of ideals, and other notions.
Apr 24Noncommutative Fourier analysis of partially ranked data
Luis David Garcia, Department of Mathematics and Statistics, Sam Houston State University
Suppose that you are given the result of a survey in which participants are asked to identify their top \(k\) choices out of \(n\) items, e.g., the preferred 3 types of cookies out of 6 Girl Scout cookies. There are several natural summaries of the number counts in this data. For example, we could consider the total number of voters approving of each different \(k\)-subset of the \(n\) candidates. We could also count the number of voters approving of each individual candidate, or the number of voters approving of each different pair of candidates, or more generally the number of voters approving of each different \(i\)-subset of the \(n\) candidates. This gives rise to a nested collection of summary statistics that could be used to describe the result of this survey. A natural question to ask is which of these summary statistics best describe the result of our survey? Which statistics capture all the “juice" in the data? About two decades ago, Persi Diaconis proposed using Fourier analysis and algebraic techniques to answer these type of questions for the case of fully ranked data. However, very little is known for the case of partially ranked data. In this talk, we will give an elementary introduction to the Fourier analysis and algebraic techniques involved in the study of both fully and partially ranked data.
May 1Melody Chan, Department of Mathematics, Harvard University