## Colloquium

#### Upcoming Seminar

December 3,
4:10 PM
in
Physics 123*Categorification*

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.

Category theory provides a framework for the process of categorification, but it is not straightforward or canonical. In this talk we will compare and contrast two methods: enrichment, in which the morphisms of a category are equipped with extra structure, and internalisation, in which the entire category is computed inside another one. We will briefly show how these methods work and how they diverge from one another by examining how they have been applied to vector spaces by Kapranov-Voevodsky, Baez and Baez-Crans.

While some familiarity with category theory will of course be useful, we will not actually assume any.

Eugenia Cheng was recently a guest on The Late Show with Stephen Colbert: http://www.eater.com/2015/11/

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.

### 2015-16 Schedule

#### Fall

**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 TheoremJohn 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 PapersJosh Gancher, Alex Ledger; Ricardo Rojas-Echenique; Riley Thornton; Nico Terry Joshua Gancher and Alex Ledger: Verifiably Secure ORAMRicardo Rojas-Echenique: Necessary and Sufficient Conditions for the Injectivity of the Dress MapNico Terry: A Few Neat Tricks with Quadratic Forms and Pfister FormsRiley Thornton: The Homogeneous Spectrum of Milnor-Witt K-Theory |

Sept 24 | Hat Guessing GamesPuck 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. |

Oct 1 | Please note change in location.Password HashingJesse Walker, Intel Location: Psychology 105This 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 ProblemAnnie 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 systemsGireeja 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 AnalysisMartina 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 SchemesAlex 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. |

Dec 3 | CategorificationEugenia 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/ |

#### Spring

**4:10-5:00** in **Eliot 314** (unless marked otherwise). Directions to Reed.

*Seminar schedule coming soon.*