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.
4:10-5:00 in Physics 123 (unless marked otherwise). Directions to Reed.
|Sept 3||Meeting with majors. No talk this week.|
|Sept 10||Probabilistically Checkable Proofs and the PCP Theorem|
John Wilmes '10, Ph.D. candidate, Department of Mathematics, University of Chicago
The mathematical proofs one usually encounters are fragile: a single error anywhere can render them invalid. Checking the correctness of such a proof requires careful reading of every line. However, this fragility is not a necessary feature of proofs in general. One of the most surprising advances in theoretical computer science is the construction of Probabilistically Checkable Proofs (PCPs), proofs whose correctness can be guaranteed with arbitrarily high confidence by spot-checking a few random locations. In fact, the PCP Theorem says, loosely, that any reasonable proof can be rewritten as a reasonably-sized PCP. In this talk, I'll discuss how to formalize the notion of a proof, give a precise statement of the PCP Theorem, and explain some elements of its proof.
|Sept 17||Student Research Papers|
Josh Gancher, Alex Ledger; Ricardo Rojas-Echenique; Riley Thornton; Nico Terry
Joshua Gancher and Alex Ledger: Verifiably Secure ORAM
Ricardo Rojas-Echenique: Necessary and Sufficient Conditions for the Injectivity of the Dress Map
Nico Terry: A Few Neat Tricks with Quadratic Forms and Pfister Forms
Riley Thornton: The Homogeneous Spectrum of Milnor-Witt K-Theory
|Sept 24||Hat Guessing Games|
Puck Rombach, Department of Mathematics, UCLA
Hat guessing games, in which players in a game have to guess the color of the hat they are wearing based on the colors of hats of other players, are popular riddles amongst puzzle enthusiasts. Numerous variants have been considered by many authors. In the most popular variant, n players are assigned a black or white hat uniformly and independently at random. They can all see each other’s hats, and they wish to maximize the probability that everybody guesses the color of their own hat correctly. Much of the popularity of this puzzle is owed to the striking difference between the probability achieved by each player guessing independently and the one achieved by an optimal strategy; (1/2)^n and 1/2, respectively. This basic problem can be generalized to directed graphs with an arbitrary number of colors. This general guessing game is equivalent to finding protocols for network coding and there is a strong connection between optimal strategies on a graph and graph entropy. We will discuss some new results and strategies, focusing on guessing games on odd cycle graphs.
Please note change in location.Password Hashing
Jesse Walker, Intel
Location: Psychology 105
This talk discusses password hashing – what it is, why it was introduced, how it has been built in the past, and why Moore’s Law has undercut the effectiveness of classical solutions. It will then discuss the Pebble Game for direct acyclic graphs and its application to time-memory tradeoffs in algorithm designs. The talk will close by discussing the Catena algorithm, one of the finalist algorithms in cryptography’s international password hashing competition that most clearly illustrates this circle of ideas.
|Oct 8||Why should we care about category theory?|
Professor Angélica Osorno, Department of Mathematics, Reed College
One of the first mathematical concepts we learn as children is counting, and when we do so, we think of counting the number of elements in a specific set. Soon after, we forget about sets and we just consider the abstract numbers themselves. This abstraction simplifies many things, but it also makes us forget about some structure that we had when we were thinking about sets. That structure can be encoded by a category. In this talk we will describe certain concepts in category theory, and you will realize that in most of your mathematics classes you have been working with categories, you just didn't know about it. There will be plenty of examples that will show that category theory provides a unifying language for mathematics, and that many constructions are more naturally understood when they are seen through the categorical lens.
|Oct 15||Turan's Problem|
Annie Raymond, Department of Mathematics, University of Washington
What is the maximum number of edges in a graph on n vertices without triangles? Mantel's answer in 1907 that at most half of the edges can be present started a new field: extremal combinatorics. More generally, what is the maximum number of edges in a n-vertex graph that does not contain any subgraph isomorphic to H? What about if you consider hypergraphs instead of graphs? We will explore different strategies to attack such problems, calling upon combinatorics, integer programming, semidefinite programming and flag algebras. We will conclude with some recent work where we embed the flag algebra techniques in more standard methods.
This is joint work with Mohit Singh and Rekha Thomas.
|Oct 22||Fall break|
|Oct 29||Information flows and bottlenecks in modern systems|
Gireeja Ranade, Microsoft Research
In 1948, Claude Shannon's seminal paper, "A mathematical theory of communication," revolutionized the field of communication and initiated the study of modern information theory. Today --- nearly seventy years later --- we are in the world of the "Internet of Things." Diverse devices are equipped with sensors, actuators, wireless transmitters-receivers and possibly computers and aim to seamlessly interact with each other and the physical world.
These developments mean that the boundaries between the sister fields of communication, control and computation are blurring and there are important questions to be understood at the intersection of these fields. This talk will provide a brief introduction to the classical ideas of information theory such as Shannon communication capacity (the fundamental limit on the rate of reliable communication through an unreliable channel). It will build to discuss information flows in control systems and introduce the new notion of "control capacity," as the fundamental limit on controlling a system through an unreliable actuator. The ideas in the talk will be built up using simple models and will draw on tools from a variety of fields including probability, information theory, computer science and control.
|Nov 5||Statistical Models for Network Analysis|
Martina Morris '80, Department of Sociology and Statistics, University of Washington
The past 10 years have seen a rapid growth in the development of statistical methodology for the empirical analysis of network data. Network data are distinctive in two ways: there are two units of analysis (nodes and links), and the observations are dependent (both within and between unit). The progress has been driven in large part by the development of computational methods for estimation, in particular, Markov Chain Monte Carlo (MCMC) methods. This talk will give an overview of the new methods and their foundation, with applications in both cross-sectional (static) and temporal (dynamic) networks.
|Nov 19||Automated Analysis and Synthesis of Authenticated Encryption Schemes|
Alex Malozemoff, Ph.D. Candidate at the University of Maryland
Encryption allows a message to be sent confidentially over a public channel. Authenticated encryption (AE) further allows the receiver to verify the source of the message. Although various AE schemes are known, there remains significant interest in developing schemes that are more efficient, meet even stronger security notions (e.g., misuse-resistance), or satisfy certain non-cryptographic properties (e.g., being patent-free).
I will present recent work published at ACM CCS 2015 in which we develop an automated approach for analyzing and synthesizing blockcipher-based AE schemes. Our main insight is to restrict attention to a certain class of schemes that is expressive enough to capture several known constructions yet also admits automated reasoning about security. We use our approach to generate thousands of AE schemes with provable security guarantees, both known (e.g., variants of OCB and CCM) and new. Implementing two of these new schemes, we find their performance competitive with state-of-the-art AE schemes.
|Nov 26||Thanksgiving. No talk this week.|
Eugenia Cheng, School of Mathematics and Statistics, University of Sheffield
Categorification may be thought of as the general process of adding taking a theory of something and making a higher-dimensional version. The aim is to express greater subtleties and more closely model the higher-dimensional structures that appear in various branches of modern mathematics including homotopy theory, cohomology, K-theory, sheaves, topological quantum field theory, as well as in theoretical physics and theoretical computer science.
Eugenia Cheng was recently a guest on The Late Show with Stephen Colbert: http://www.eater.com/2015/11/
4:10-5:00 in Physics 123 (unless marked otherwise). Directions to Reed.
Please note change in date.Invariants of Singular Spaces
Jesse Gell-Redman, Johns Hopkins University
One of the fundamental distinctions in mathematics is that between the local and global invariants of a space. A global invariant is a property of a shape that depends on how the space looks in its entirety, i.e. from far away. Examples include the number of sides a polygon has or the number of holes in a surface. (Does the surface look like a basketball, so zero holes, or like a doughnut, so one hole?) Local invariants come from the actual geometry itself, the main example being a numerical measure, called the Gauss curvature, of how much a space is curved at a given point.
As I will explain, local and global invariants of spaces are related in a profound way. Although this relationship has been known for a long time, it is not well-elaborated in the context of singular spaces, i.e. shapes like cones or horns which have a point or points that are not smooth. That would be fine, were it not the case that some of the most interesting geometries that arise in mathematics and physics are singular! I will illustrate the latter statement with simple examples and explain how progress can be made understanding invariants of these spaces.
|Jan 28||An Inverse Problem in Spectral Geometry|
David Sher, University of Michigan
Consider a physical object, such as a drumhead, that vibrates when struck. The motion of the drumhead may be understood in terms of its resonance frequencies and modes of vibration. In spectral geometry, we study the relationship between these resonance frequencies - mathematically, the spectrum of the Laplace operator - and the geometry of the drumhead. A key question is the *inverse spectral problem*: what can we deduce about the geometry from the spectrum? That is, if we know the resonance frequencies of a drumhead, what can we say about its shape? This question may be asked in a variety of different contexts. One such context involves the Dirichlet-to-Neumann operator, which appears in problems ranging from medical imaging to hydrodynamics. In this talk, I will first give an overview of the types of questions we ask in spectral geometry. I will then discuss several recent results on the spectral geometry of the Dirichlet-to-Neumann operator, with particular emphasis on the inverse spectral problem.
Please note change in date.Fair Computation with Rational Parties
Adam Groce, Reed College
Traditional cryptography requires that regardless of what malicious parties might do, security still holds. Rational cryptography instead uses game theory to model behavior. It assumes that the parties in question have goals and will misbehave only if it furthers those goals. In this talk, I'll introduce rational cryptography and show how it can be used to accomplish the otherwise impossible.
In particular, we’ll look at secure computation, which allows parties who each have one input to compute a function of those inputs without sharing them with each other. Depending on the function chosen, secure computation can allow electronic voting that keeps votes anonymous or allow companies to collaborate without sharing proprietary data. It is one of the most general and powerful primitives in all of cryptography. Unfortunately, traditional protocols are all "unfair," meaning that one party can get the answer but prevent other parties from seeing it. In contrast, I will show a fair rational-secure protocol, circumventing two separate impossibility results.
Please note change in date.
Please note change in location.Derandomization, Lower Bounds, and Polynomial Identity Testing
Matt Anderson, Union College
Location: Eliot 314
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 computational 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 (PIT). 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. This is difficult question, in part, because providing such an efficient PIT algorithm would imply a strong circuit lower bound, that is, it would demonstrate a computational problem that cannot be solved efficiently by any deterministic algorithm. The search for such lower bounds is a central, long-standing open question in Computational Complexity Theory.
One line of my research approaches answering these questions by examining them in more restricted models of computation. I will discuss efficient deterministic identity tests and lower bounds I developed for several arithmetic models of computation. I conclude by discussing possible extensions to these works and other research topics I am interested in, including a number of ideas for (summer) research projects and senior theses.
|Feb 4||Elliptic equations with vanishing coefficients and regularity of solutions|
Lyudmila Korobenko, McMaster University
Among the central questions of Partial Differential Equations is existence and uniqueness of solutions and their regularity. It turns out that to define a solution to a second order partial differential equation it is not necessary to require a function to be twice differentiable, instead one can define the so called ``weak solutions''. The advantage is that it is relatively easy to show the existence and uniqueness of such solutions, however, the question arises whether they are differentiable or even continuous. We are interested in Elliptic equations that generalize well known Laplace's and Poisson's equations which arise in many areas of physics, such as electromagnetism, fluid dynamics, and mechanics. The study of solutions to elliptic equations goes back to 18th century and the properties of solutions are well known. If we consider equations with variable coefficients that can vanish at certain points the theory becomes much more complicated and thus much more interesting. I will talk about weak solutions to elliptic equations and a method to show their regularity called Moser iteration. I will then show how this method can be applied to study equations with vanishing coefficients, called degenerate elliptic equations. I will also talk about some new results in this area, including the results my collaborators and I have recently obtained for infinitely degenerate elliptic equations.
Please note change in date.Helping Software Exploit Hardware
Kelly Shaw, University of Richmond
Software developers frequently write code in a manner that abstracts away the details of the hardware on which the software will run. While this software will execute on many computing platforms, it will not run as quickly or efficiently as it could if the software took advantage of hardware specific characteristics. Unfortunately, optimizing programs for specific hardware is a time intensive process, making it unlikely that applications will be optimized for many hardware configurations.
In this talk, I present two approaches we created to help developers write high performance software for graphics processors. Starchartenables developers to systematically and quickly understand how to tune important characteristics of their applications for different hardware. The second approach, called MRPB, automatically prioritizes and reorders data accesses to increase the benefits obtained from data caching in graphics processors. Both approaches ease the software developer's burden when writing and optimizing software for graphics processors.
Please note change in date.
Please note change in location.Improving Password Security and Usability through Data-Driven Approaches
Blase Ur, Carnegie Mellon University
Location: Eliot 314
Users often must make security and privacy decisions, yet are rarely equipped to do so. In my research, I aim to understand both technical systems and the humans who use them. Armed with this understanding, I design approaches and systems that help users protect their security and privacy.
In this talk, I will describe how I applied this research approach to password security and usability. As understanding what makes a password good or bad is crucial to this process, I will first discuss my work on metrics for password strength. These metrics commonly involve modeling password cracking, and I found that the approaches often modeled by researchers vastly underestimate passwords' vulnerability to experts in password forensics. I instead propose combining a series of carefully configured approaches, which I found to conservatively model experts. I used these insights to design a Password Guessability Service, which I have opened to the community to enable more robust research. I will then highlight my work on another key step, investigating how humans create and perceive passwords. I will focus on the impact of password-strength meters, users' perceptions of password security, and my ongoing efforts to develop a better password-strength meter. By combining better metrics with an understanding of users, I am able to design approaches and systems that guide users towards better passwords.
Please note change in location.Math curriculum discussion (for students only)
Location: Psych 105
Significant changes to the mathematics curriculum and major at Reed will be introduced next fall. We are introducing new courses and eliminating or restructuring others. We are also rewiring the requirement structure for our courses and for the major. Reed community members are invited to learn about and discuss these changes.
|Feb 25||Cascadia Subduction Quakes: Data, Models and Uncertainty|
Albyn Jones, Reed College
A recent New Yorker article ("The Really Big One", July 20, 2015) is subtitled "An earthquake will destroy a sizable portion of the coastal Northwest. The question is when." We will look at the evidence, consider (possibly) relevant probability models, and assess the uncertainty that remains in forecasts of the risk.
|Mar 3||Homotopy, Manifolds, Cobordisms, and Genera|
Kyle Ormsby, Reed College
Amongst other things, algebraic topologists concern themselves with
In this talk, I will explore the interplay between these concepts, ultimately arriving at the Witten genus and a way to use modular forms to detect homotopy groups.
Please note change in date.Geometric transitions in dimensions 2 and 3
Kenji Kozai, University of California, Berkeley
Geometry plays an important role in understanding topology in dimensions 2 and 3. In dimension 2, surfaces admit one of three geometries: Euclidean, spherical, and hyperbolic. I will explain these three geometries with pictures and examples, why understanding these geometries gives information about the surface, and how some surfaces like the three-holed sphere admit a one parameter family of geometric structures that transition between all three types of geometries. I will then discuss the situation in dimension 3, where Perelman's Geometrization Theorem shows that there are eight different geometries, and work of Cooper-Danciger-Wienhard describes which geometries can transition into others.
|Mar 10||Topology of Configurations on Trees|
Safia Chettih, University of Oregon
Configuration spaces of graphs have a rich network of connections to many areas of mathematics, while some basic properties of these spaces elude a general description. This talk will introduce some fundamental tools of algebraic topology, the better to understand these spaces with, and touch on a discretized model for configuration spaces of graphs which has made deeper insights possible. The goal is a complete understanding of the first homology group of configurations of two points in a tree, both combinatorially and geometrically, with an eye towards the grander structure these results reveal.
Please note change in date.Representations of elementary abelian p-groups.
Shawn Baland, University of Washington
Groups like to act on sets! One of the best examples of this is when elements of a group G act linearly on a vector space V, in which case we cal V a G-module. Group representation theory is the study of G-modules. In this talk I will discuss the representation theory of elementary abelian p-groups. We will see that, although the structures of such groups are not very complex, their representations are rather difficult to understand. The overall goal will be to compute some interesting examples using matrices and diagrammatic techniques. I will also outline some current problems in the area.
|Mar 17||Solutions of Polynomial Equations: Not So Easy After All|
Mckenzie West, Emory University
Polynomial equations and their solutions form a cornerstone of mathematics. Solutions with rational coordinates are particularly intriguing; a fantastic surprise is the great difficulty of determining the mere existence of a rational solution to a given equation (let alone the complete set). A surprising and successful modern approach, the Brauer—Manin obstruction, employs tools from geometry and non-commutative algebra. I will discuss a collection of interesting and motivating examples with simultaneous historical and modern interest, and also explain some of the tools and techniques that form the backbone of my research program.
|Mar 24||Spring Break|
Please note change in date.Transfer maps in geometry, algebra, and topology
John Lind, Universität Regensburg
Transfer maps (also known as "umkehr" or wrong-way maps) are certain sorts of functions that go in an unexpected direction. In other words, their source and target are opposite from what is expected in the given context. Transfer maps can provide surprisingly deep information about the objects that they are defined on. I will show you some examples that you already know very well, and then will describe a more exotic transfer map that arises by understanding the geometry of loops in an algebraic way.
Please note change in date.
Please note change in location.Analytic properties of the Riemann zeta function and beyond
Mark McKee, University of Iowa
Location: Eliot 314
In this talk, I will first show Riemann's original proof that the zeta function can be continued (in a complex differentiable way) to the complex plane. I will develop the analytic tools from scratch. Then I will talk about the important hypothesis related to zeta, as well as how the Prime Number Theorem is related. I will mention certain natural bounds zeta has, as the variable goes to infinity. One property is called convexity. I will then give a glimpse of higher dimensional L-functions (generalizations of zeta), and current work on breaking the convexity bounds.
|Mar 31||Continuous families of vector spaces|
Jeremiah Heller, University of Illinois Urbana-Champaign
The notion of a continuous family of vector spaces, aka a vector bundle, is an ubiquitous one in topology, geometry, and algebra. For example, given a manifold, the collection of tangent vectors at the points of the manifold assemble into such an object, the tangent bundle. Focusing on this example, in this talk we'll take a look at some of the deep geometric and algebraic structures captured and reflected by vector bundles. By the end of the talk, you will have an answer to the riddle, "What is the difference between a coconut and the CERN particle accelerator?".
|Apr 7||Homotopy and Type Theory|
Steve Awodey, Carnegie Mellon
Recently, a new connection was discovered between Homotopy Theory, the branch of mathematics that studies continuous deformations of spaces and their mappings, and Type Theory, a system of foundations originally invented as an alternative to set theory and now used as the basis of computerized proof checkers. This discovery has given rise to some new ideas about the possibility of homotopical foundations, and new computer systems for checking proofs in homotopy theory. This introductory talk will explain some of these recent developments.
|Apr 14||Elliptic curves and a theorem of Pascal|
Dan Dugger, University of Oregon
This talk will be an excursion in projective geometry. We will look at the classical theorems of Pappus and Pascal dealing with collinearity of certain intersection points derived from a hexagon, and then see how these fit into the more modern perspective of Bezout's theorem. I will then discuss the group law on a projective elliptic curve, and how associativity connects to these classical theorems. Theoretically, this could all be understood by a high school math student. To keep that from happening I will try to use as many big words as possible.
|Apr 21||Shapes of numbers|
Vesna Stojanoska, University of Illinois Urbana-Champaign
Take a natural number n, and look at all possible ways to break up the numbers from 1 to n into several groups. These are called partitions. Two partitions are linked if one can be obtained from the other by breaking up some groups. Three partitions are linked if one is obtained from the other by breaking up, and the third is obtained by breaking up further. Similarly, we can define when any number of partitions are linked. Studying these linkage properties gives rise to a shape associated to the number n, whose symmetries know about deep structures in algebraic topology.
|Apr 28||Knots and Numbers|
Haynes Miller, Massachusetts Institute of Technology
The Jones polynomial revolutionized knot theory thirty years ago. I will describe a variant of this knot invariant suitable for studying Conway tangles. This provides an example of an optimal theorem in algebraic topology - a complete invariant of a class of geometric objects. I will provide a proof of this result, and verify it with a square dance.