# Mathematics Department

## Colloquium

#### Upcoming Seminar

April 30, 4:10 PM in Physics 123
Branch, Bound, and Kill: a Family-Friendly Algorithm for Statistical Inference
Andrew Bray, Five College Consortium and Reed College

Of central importance to statistical modeling is the likelihood function: the function that expresses all of information held in a data set in the context of a particular statistical model. Despite its centrality to the statistical process, the likelihood is often frustratingly difficult to deal with analytically. Of particular interest are the regions where these functions are high, and to find them statisticians often resort to general optimizing algorithms that may fail to find the global optimum. In this seminar we'll discuss branch and bound style algorithm that evaluates the function to an arbitrary degree of precision within a given region of the parameter space, ensuring that no optima are excluded.

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.

### 2014-15 Schedule

#### Fall

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

Sept 4 Meeting with majors. No talk this week. The Combinatorics of CAT(0) Cubical Complexes and Robotic Motion PlanningFederico Ardila, Department of Mathematics, San Francisco State UniversityA cubical complex is CAT(0) if it has global non-positive curvature; informally, "all its triangles are thin". These complexes play an important role in pure mathematics (group theory) and in applications (phylogenetics, robot motion planning, etc.). In particular, as Abrams and Ghrist observed, when one studies the possible states of a discrete robot, one often finds that they naturally form a CAT(0) cube complex. Gromov gave a remarkable topological/combinatorial characterization of CAT(0) cube complexes. We give an alternative, purely combinatorial description of them, allowing a number of applications. In particular, for many robots, we can use these tools to find the fastest way to move from one position to another one. The talk will describe joint work with Tia Baker, Megan Owen, Seth Sullivant, and Rika Yatchak. It will require no previous knowledge of the subject, and be accessible to undergraduate students. Leadership Summit Dissecting a square into trianglesJamie Pommersheim, Mathematics Department, Reed CollegeYou can do this in many ways. You can even arrange for all the triangles have exactly the same area. However, an old theorem (1970) of Paul Monsky asserts that it is impossible to cut a square into an odd number of triangles of equal area.  The proof of this theorem is a delightful blend of geometry, combinatorics, and number theory. This aim of this talk is to prove Monsky’s Theorem and understand some of the geometrical, combinatorial, and algebraic ingredients that go into its proof. The talk may also serve as motivation for Aaron Abrams’s talk next week (October 2), in which Aaron will probably discuss a current research project which grew out of a desire to better understand Monsky’s Theorem. Triangulations of a square and Monsky polynomialsAaron Abrams, Mathematics Department, Washington and Lee UniversityThis will be a sequel to Jamie's talk from 9/25, but his talk is not a prerequisite. The main theorem of his talk is that it is impossible to cut a square into an odd number of triangles of equal area. In my talk we will explore, more generally, what restrictions there are on the areas of triangles in a triangulation of a square. It turns out that for each combinatorial type of triangulation, there's a polynomial relation that must be satisfied by the areas. I will describe some of the things we know about this polynomial. Student PresentationsMaddie Brandt, Joshua Gancher, Justin KatzMaddie Brandt: Packing Polynomials on Sectors of $$\mathbb{R}^2$$ Abstract: A polynomial $$p(x,y)$$ on a region $$S$$ in the plane is called a packing polynomial if the restriction of $$p(x,y)$$ to $$S\cap \mathbb{Z}^2$$ yields a bijection to $$\mathbb{N}$$. In this talk, we classify all quadratic packing polynomials on rational sectors of $$\mathbb{R}^2$$. Joshua Gancher: Weierstrass Points on Graphs Abstract: TBA Justin Katz: A primary decomposition in computer vision ﻿Abstract: The pinhole model for a projective camera is given by a projective plane $$P$$ and a focal point $$p$$, embedded in an ambient 3-dimensional projective space. The image of a point $$x$$ in the projective space under the pinhole camera is given by the unique point of intersection between the line connecting $$x$$ and $$p$$ and the image plane $$P$$. Given a collection of distinct pinhole cameras, the image of a point in any one image plane constrains the possible corresponding points in the other image planes. Analyzing a camera system by considering pairs of cameras determines a bilinear constraint polynomial on the image coordinates, and considering triples of cameras determines a related trilinear polynomial constraint, known as the trifocal tensor. This talk will consider the ideal generated by selecting a particular subset of bilinear constraints, and demonstrate that the whole ideal generated by the trilinear constraints arises as a primary component. Such a primary decomposition has the potential to speed up image matching algorithms. Higher-Dimensional Pick's Theorems and Strange Ways of CountingBen Fischer '09, Department of Mathematics & Statistics, Boston UniversityPick's Theorem relates the area of a two-dimensional polyhedron to the number of integer points in each face. The theorem is patently false in three or more dimensions, but in this talk I will describe (infinitely many) ways of constructing higher-dimensional analogues. In order to do so, it will be helpful to generalize the notions of "volume" and "number of integer points", in order to give us something meaningful even when the polyhedron is unbounded. This is joint work with Jamie Pommersheim that evolved out of my senior thesis at Reed in 2009. No prior familiarity with polyhedra will be assumed - only a basic knowledge of linear algebra and calculus. Fall break Computing Siegel Modular Forms by the Pullback-Genus MethodJerry Shurman, Mathematics Department, Reed CollegeSiegel modular forms are important.  Also, they are enormous and unwieldy, prohibitive to work with by hand and computationally daunting. A formula due to Garrett shows that all Siegel modular forms of a given degree are encoded by one particular modular form of twice the degree, the Eisenstein series.  Work of Siegel and Katsurada shows that the Eisenstein series is more computationally tractable than a general Siegel modular form, providing some counterbalance to its having twice the degree.  Poor and Yuen have devised and implemented an algorithm that uses these ideas to compute Siegel modular forms, finding new examples of degree 3 and identifying them. This talk will attempt to explain some of these matters. Secure Multiparty ComputationAdam Groce, Mathematics Department, Reed CollegeImagine two companies are trying to decide the merit of merging. Doing so requires comparing the books and client lists of the two companies, but both are reluctant to show this proprietary information to each other. Is there a way for them to do these complicated financial calculations without either seeing the other’s books? Secure multiparty computation (MPC) gives us a way to do exactly this sort of joint computation. In this talk we will see how it’s done. On the way, we’ll see how modern cryptography defines security for a problem like this and we’ll look at encryption, oblivious transfer, and other tools that are used in solving it. We’ll also take a quick step away from the theoretical work to look at how MPC results are being used in the real world. Please note change in date.Random multigraphs and a method for finding hidden relationships in networksJohn Rañola, Department of Biomathematics, University of California Los AngelesNetworks are often modeled by random graphs, a model where every pair of nodes is either connected by an edge or not. In Facebook and other social networks, random graphs are often formed by joining a pair of nodes, in this case people, if they are friends on the site. Although this is useful for some purposes, a lot of information is lost to the model. Attributes such as the number of messages or the number of “likes” exchanged can give more information than simply friends or not friends. In this talk, I will present a random multigraph model where every pair of nodes can be connected by multiple edges such as the number of messages exchanged. Under certain assumptions, I will show that the model can be used to find pairs of nodes that have relationships unlike the others. In the Facebook example, the special pairs of nodes may be best friends, family members, sweethearts, or something other than friends. I will present results from applying this model to various real data including neuronal connections, interacting genes in radiation hybrids, letter and word pairs in seven Shakespearean plays, and Fortune 500 companies connected by shared board members. Please note change in date.Predicting First Flowering Events Using Survival ModelsMaria Terres, Department of Statistical Science, Duke UniversityFirst flowering events in cherry trees are believed to be closely related to temperature patterns during the winter and spring months. Earlier works have incorporated the idea of temperature thresholds, defining chill and heat functions based on these thresholds. However, selection of the thresholds is often arbitrary and shared across species and locations. We propose a survival model with spatially and temporally varying covariates having functional forms representing chill and heat accumulation leading up to first flowering events. Thresholds are chosen utlizing the ranked probability scores, selecting the threshold pair that minimizes the difference between the predicted and observed cumulative probability curves. We first apply the model using temporally varying covariates to analyze 29 years of flowering data for four cherry species (Cerasus spp.) grown in Hachioji, Japan. This allows us to investigate whether relationship with temperature may vary between earlier and later flowering species. Next, the model is applied to 52 years of flowering data for 45 Cerasus spachiana × C. speciosa trees grown across Japan's Honshu Island using spatially and temporally varying covariates and spatial random effects. By exploring flowering dates across locations, we can explore how the relationship between temperature and first flowering events varies through space. Finally, these models are used to predict shifts in flowering due to climate change based on output from an ensemble of three regional climate models. Complications of Compliance in Causal InferenceDavid Watson, Department of Statistics, Harvard UniversityRandomized experiments are the gold standard for estimating causal effects of an active treatment compared to a control treatment.  However, complications of compliance often arise when subjects do not take the treatment assigned to them.  We consider the case of one-way compliance in which some subjects decline to take the active treatment when assigned.  In such cases, the standard "intention-to-treat" analysis is still justified, but results must be interpreted as a causal effect of assignment to treatment as opposed to receipt of treatment.  Of course, investigators primarily care about the effect of the treatment for subjects who would actually receive the treatment.  This idea motivates estimating the causal effect for a latent, or partially observed, subgroup of subjects called the compliers.  We describe how to estimate the complier average causal effect under certain assumptions and show how naive estimators based on the observed treatment received do not have a causal interpretation.  We use a clinical trial of an intervention for high cholesterol patients as a motivating example. Please note change in date.Markov Chain Monte Carlo Estimation for Bayesian Disease Cluster DetectionAlbert Kim, Mathematics Department, Reed CollegeWe consider the problem of detecting clusters of non-infectious and rare diseases.  A class of cluster detection methods known as scan statistics superimpose a large number of circles onto a study region.  For each of these circles, the significance of any excess of observed cases over what is expected is determined under the null hypothesis of equal risk of disease inside and outside the circle.  These circles form the basis of our Bayesian model which identifies individual areas with high posterior probability of being in a disease cluster.  The method incorporates prior information about disease clusters and accounts for multiple clusters simultaneously. After presenting an application of the method to brain and breast cancer in Western Washington state, we discuss the Markov Chain Monte Carlo method used to estimate all discrete posterior quantities.  In particular we focus on the issue of improving the efficiency of the algorithm, which is paramount when considering large study regions and when further extending the methodology to detect spatio-temporal clusters. Thanksgiving. No talk this week. Euler characteristic: an introduction to thinking topologicallyAnna Marie Bohmann, Mathematics Department, Northwestern UniversityYou may have encountered the concept of Euler characteristic when thinking about soccer balls or Euclidean solids. We'll discuss counting and Euler characteristic: counting points, counting potatoes, and counting holes.

#### Spring

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

Jan 29 Mathematical Models for HIV Transmission NetworksMartina Morris, Departments of Sociology and Statistics, University of WashingtonSince the beginning of the HIV epidemic, mathematical models have been used as a virtual laboratory for projecting how the infection is likely to spread.  Now, 30 years into the global pandemic, new biomedical interventions -- early treatment (Treatment as Prevention or TasP) and pre-exposure Prophylaxis (PreP) -- are leading many to predict the "End of AIDS".  Increasingly sophisticated models lie behind these optimistic projections.  This talk will take a look behind the curtain to see what these models include and what they assume, the new developments in modeling networks that challenge these findings, and the politics behind the math. Please note change in location.Design of 3D Printed Mathematical ArtHenry Segerman, Department of Mathematics, Oklahoma State UniversityLocation: Psych 105When visualising topological objects via 3D printing, we need a 3-dimensional geometric representation of the object. There are three broad strategies for doing this: "Manual" - using whatever design software is available to build the object by hand; "Parametric" - generating the desired geometry using a parametrisation of the object; and "Iterative" - numerically solving an optimisation problem. The manual strategy is unlikely to produce good results unless the subject is very simple. In general, if there is a reasonably canonical geometric structure on the topological object, then we hope to be able to produce a parametrisation of it. However, in many cases this seems to be impossible and some form of iterative method is the best we can do. Within the parametric setting, there are still better and worse ways to proceed. For example, a geometric representation should demonstrate as many of the symmetries of the object as possible. There are similar issues in making 3-dimensional representations of higher dimensional objects.  I will discuss these matters with many examples, including visualisation of 4 dimensional polytopes (using orthogonal versus stereographic projection) and Seifert surfaces (comparing my work with Saul Schleimer with Jack van Wijk's iterative techniques). I will also describe some computational problems that have come up in my 3D printed work, including the design of 3D printed mobiles (joint work with Marco Mahler), "Triple gear" (joint work with Saul Schleimer), and hinged surfaces with negative curvature (joint work with Geoffrey Irving). Please note change in date.Experimentation and Testing for Social GoodKaty Davis '02, Reed Alumna, Currently with ideas42Behavioral science teaches us that humans often behave quite differently from how we might expect. At ideas42, we use insights from behavioral science to better design programs and policies for social good. And because we understand the "quirks" of human perception, we rigorously test all of our designs using Randomized Controlled Trials (RCTs). In this talk, I will outline some basic principles of behavioral science, discuss why and how we run experiments and analyze data in the social sector, and walk through a quick case study of actual data analysis results. You Can't Hear the Shape of an OrbifoldLiz Stanhope, Mathematics Department, Lewis & ClarkIf we can infer the chemical composition of a star from the colors of light it emits, can we determine the shape of a bell from the ringing that it makes?  One way to address this question is to ask if the eigenvalues of the Laplace operator associated to a Riemannian manifold determine the manifold.  A famous answer of "No" came in 1992 when Gordon, Webb and Wolpert exhibited nonisometric planar domains with exactly the same Laplace spectrum.  After an introduction to the mildly singular spaces known as Riemannian orbifolds, I will discuss the degree to which the Laplace spectrum of an orbifold gives us information about the geometry and topology of the orbifold. Please note change in date.Looking at the Common Core State Standards in Mathematics as a mathematical document and as a knowledge network.Dev Sinha, Mathematics Department, University of OregonQuick question - how do you know that 28 x 35 is the same as 35 x 28?  How do you really know?? The Common Core State Standards in Mathematics can be read simultaneously as a policy document, as a pedagogical document, and as a mathematical document.  We will focus on the latter two, in particular starting with how it gives what are essentially proofs throughout K-12 mathematics, for almost every topic which does not require limits.  We will then look at this mathematico-pedagogical structure as a network or even simplicial complex, and speculate about the role of this structure in cognition and learning. A Stable Marriage Requires CommunicationWill Rosenbaum '09, Department of Mathematics, UCLAIn this talk, we introduce the stable marriage problem, a classical problem in discrete math, economics, and computer science. Following the celebrated work of Gale and Shapley, we describe a simple algorithm which efficiently finds a stable marriage for any instance of the problem. After a brief foray into the world of communication complexity, we prove communication lower bounds for the stable marriage problem. As a consequence, we are able to show that Gale and Shapley's algorithm is, in a very strong sense, optimal. This talk presumes only high-school level mathematics, and should appeal to anyone with an interest in discrete math, economics, or computer science. The range of deterministic random walksLaura Florescu '11, Courant Institute of Mathematical Sciences, New York UniversityIn a deterministic random walk on a graph, the exits from each vertex follow a prescribed periodic sequence. We show that any such walk on the $d$-dimensional lattice $\Z^d$ visits at least on the order of $t^{d/(d+1)}$ distinct sites in $t$ steps. In a uniform deterministic random walk the first exit from each vertex is to a neighbor chosen uniformly at random. We prove a shape theorem for the uniform walk on the comb graph, showing that the range is of order $t^{2/3}$ and the asymptotic shape of the range is a diamond. Using a connection to the mirror model we show that the uniform rotor walk is recurrent on two different directed graphs obtained by orienting the edges of the square grid, the Manhattan lattice and the $F$-lattice. Joint work with Lionel Levine and Yuval Peres. When Algebraic Geometry Meets Graph TheoryMohamed Omar, Department of Mathematics, Harvey Mudd College Many graph theoretic problems, both structural and algorithmic, have benefited from the viewpoint of linear algebra. However, very few related results have come from the application of tools from algebraic geometry. In this talk we will discuss a particular application of Hilbert's Nullstellensatz, a celebrated theorem in classic algebraic geometry, to understanding 3-colorability of graphs, and its consequences on computational complexity theory. This is joint work with Bo Li and Benjamin Lowenstein. Career Panel - for Reed students onlyChristopher Fesler '96, Laura Heiser, Greg Morgan '77, Rose Peterman '10, and Steve Swanson '84Come meet alumni and other mathematics majors to see what they are doing with their degrees!  Featuring: Christopher Fesler ‘96 - Principal Engineer at Peak6 Investments Laura Heiser - Assistant Professor of Biomedical Engineering at OHSU Greg Morgan ‘77 - Former Managing Director at Huron Consulting Group Rose Peterman ‘10 - Actuary at Regence Blue Cross Blue Shield Steve Swanson '84 - Software Engineer Manager at Elemental Technologies Spring Break How Origami Beat EuclidAna Rita Pires, Department of Mathematics, Fordham UniversityA classic exercise in geometry is to make certain constructions using only a ruler and compass. This restriction in what instruments to use was set by Euclid, the "father of geometry". Some constructions became famous for being impossible to obtain according to these rules, for example doubling the cube, trisecting the angle and squaring the circle.  But what if instead of Euclid's ruler and compass we use origami? Can origami, in addition to producing pretty paper animals, solve these problems from antiquity? Khinchin's ConstantTom Wieting, Mathematics Department, Reed CollegeThe source of the Ergodic Theorem lies in Mathematical Physics, while its tributaries supply Number Theory, Group Theory, Dynamical Systems Theory, Probability Theory, and many other territories.  The object of this lecture is to present the Ergodic Theorem in terms of a case study, drawn from the Theory of Continued Fractions.  In due course, we will encounter the celebrated Theorem of Khinchin, which for eighth decades has provoked (a mild mannered) debate between the camps of Formalism and Intuitionism in Mathematics. Deleting (Not Too Much) to Make Things SimpleGlencora Borradaile, School of Electrical Engineering and Computer Science, Oregon State UniversityGiven a graph with n vertices and m edges, did you know that you can delete m/4 vertices and leave behind a forest? It turns out that deleting fewer vertices will get you graphs that are almost as simple as forests: deleting m/4.5 vertices will get you a pseudoforest, deleting m/5 vertices will get you a partial 2-tree and deleting m/5.2174 vertices will get you a planar partial 3-tree. It also turns out that there is a limit to this: deleting m/6 vertices won't get you anything interesting. This talk will teach you what these structures are (pseudoforests and 2-trees and so on). The results are based on recent work with David Eppstein and Pingan Zhu. Magic, Braids, and Moduli SpacesNick Salter '11, Mathematics Department, University of ChicagoIf I just told you directly that this week's colloquium was going to be about math and magic tricks, you'd probably think it would be about as cool and/or interesting as this guy:  But what if I told you that I'd be talking about a magic trick invented by this guy:  And that this was some of the math involved: Then you'd probably want to come. Branch, Bound, and Kill: a Family-Friendly Algorithm for Statistical InferenceAndrew Bray, Five College Consortium and Reed CollegeOf central importance to statistical modeling is the likelihood function: the function that expresses all of information held in a data set in the context of a particular statistical model. Despite its centrality to the statistical process, the likelihood is often frustratingly difficult to deal with analytically. Of particular interest are the regions where these functions are high, and to find them statisticians often resort to general optimizing algorithms that may fail to find the global optimum. In this seminar we'll discuss branch and bound style algorithm that evaluates the function to an arbitrary degree of precision within a given region of the parameter space, ensuring that no optima are excluded.