Colloquium
Upcoming Seminar
January 26,
4:40 PM
in
P123
Equivocating Yao: ConstantRounds Adaptively Secure Multiparty Computation in the Plain Model
Muthuramakrishnan Venkitasubramaniam, Department of Computer Science, University of Rochester
We provide a positive answer to this question. We define a new type of encryption, called functionally equivocal encryption (FEE), and show that when Yao’s scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function.
Combining our scheme with noncommitting encryption, we obtain the first twomessage, twoparty computation protocol, and the first constantrounds multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. We also provide extensions to the multiparty setting (with UCsecurity) and applications to leakage resilience.
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.
201617 Schedule
Fall
4:405:30pm in Physics 123 (unless marked otherwise). Directions to Reed.
Sept 1  Meeting with majors. 

Sept 8  Private Data Analysis Adam Groce, Mathematics Department, Reed College 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 while protecting privacy. However, before such tools can be created, it is necessary to formally define the desired notion of "privacy." We will begin by talking about what definition is appropriate, and then we will look at how certain analyses can be carried out under the constraint of protecting privacy. Finally, I'll give a brief overview of recent developments in this field and what sort of challenges remain to be solved.

Sept 15  Set Theory via the Polynomial Method Joe Buhler, CCR/Reed College 
Sept 22  A Curious Monoid Keith Pardue, NSA I will describe a curious monoid* \(U\) whose elements are certain trees with colored leaves. My collaborator and I discovered this monoid through a speculation in category theory, and we were surprised and enchanted by the rich combinatorial structure that we found. I'll finish with a basic question about \(U\) that we have not been able to resolve. * A monoid is a set \(M\) with a binary operation \(M\times M\to M\) that is associative and has an identity. Elements of a monoid need not have inverses, as they must have in a group. 
Sept 29  Student research projects Chris Keane and Ricardo RojasEchenique, Reed College Chris Keane: A Combinatorial Model for Quantum Matrices Abstract: A combinatorial model for the algebra of quantum matrices was discovered by K. Casteels in 2014. After explaining the construction of the model, we will explain its relevance to the study of the prime spectrum of the algebra of quantum matrices. Specifically, we will explain how the model gives a way to interpret ideal membership for a certain class of primes, and also present how this interpretation makes it possible to compute generating sets for this class of primes. Ricardo RojasEchenique: Bijections Between the Recurrent Sandpiles of an Eulerian Digraph and its Reverse Abstract: An Eulerian digraph is a directed graph where the indegree of each vertex is equal to the outdegree. After designating a single vertex of an Eulerian digraph as a sink, the set of recurrent sandpiles on the graph forms a finite abelian group isomorphic to the cokernel of the Laplacian matrix of the graph. Given a digraph, we can also construct its reverse graph by reversing the direction of each edge. In the case of Eulerian digraphs we have the salient property that the Laplacian of the reverse graph is equal to the transpose of the Laplacian of the original graph. This allows us to conclude the two groups of recurrent sandpiles are isomorphic. While this isomorphism shows that the number of recurrent sandpiles on an Eulerian digraph and its reverse are equal, the two sets of sandpiles can look quite different. We discuss a few possible natural bijections between the recurrent sandpiles on an Eulerian digraph and its reverse. 
Oct 6  Paramodularity computations for squarefree level Jerry Shurman, Department of Mathematics, Reed College The Paramodular Conjecture of Brumer and Kramer is a degree \(2\) modularity conjecture. The analytic space in the conjecture is \({\mathcal S}_2(\operatorname{K}(N))\), the space of weight \(2\), level \(N\) Siegel paramodular cusp forms. Earlier computational work confirmed the conjecture for prime \(N\) up to \(600\), and now new work has confirmed it for nonprime squarefree \(N\) up to \(300\). The interesting new cases are \( N=249, 295\), where one form exists beyond the additive (Gritsenko) lift space of the Jacobi form space \(\operatorname{J}_{2,N}^{\rm cusp}\), as predicted by the existence of suitable abelian surfaces for those \(N\). 
Oct 13  Cancelled MNS/STEMTBA 
Oct 20  Fall break 
Oct 27  Tableaux, Hives, and Integer Triangles: Playing with puzzles to solve difficult problems Natalie Hobson, Department of Mathematics, University of Georgia Do you think solving number puzzles like Sudoku and Kenken is done just for fun? Well mathematicians have used three types of puzzle games similar to these to solve many difficult problems. Some of these problems have been open for over fifty years and still intrigue many. In this talk, we will learn how to play these puzzles, discover their beauty and structure, and investigate remaining open questions they might help us solve. 
Nov 3  Introduction to algebraic Ktheory Mona Merling, Department of Mathematics, Johns Hopkins University Algebraic Kgroups are deep invariants of rings, which hide beautiful patterns and connections to problems in number theory. Lower Kgroups have explicit algebraic descriptions, but higher algebraic Kgroups require sophisticated topological and categorical machinery to define, and their introduction by Quillen was the culminating point of a long search for a definition that would meaningfully generalize the existing definitions of lower Kgroups. In this talk, I will give a flavor of algebraic Ktheory and its history, touching on current research. 
Nov 10  Hopping Particles And Rhombic Tableaux Olya Mandelshtam, Department of Mathematics, UCLA The asymmetric simple exclusion process (ASEP) is a model from statistical physics that describes the dynamics of particles hopping right and left on a finite 1dimensional lattice. Particles can enter and exit at the left and right boundaries, and at most one particle can occupy each site. The ASEP has been wellstudied, for instance as a model for processes such as protein synthesis, molecular and cellular transport, and traffic flow. The ASEP is remarkable in that it is one of very few nonequilibrium processes for which there exist exact formulae for its stationary distribution. Moreover, it displays rich combinatorial structure: one can compute the stationary probabilities for the ASEP using fillings of certain tableaux. I will discuss some of the combinatorial results from the past decade, including recent developments. 
Nov 17  Modeling perceptual invariances in biological sensory processing Alexander Dimitrov, Department of Mathematics and Statistics, Washington State University, Vancouver The sense of hearing is an elaborate perceptual process. Sounds reaching our ears vary in multiple features: pitch, intensity, rate. Yet when we parse speech, our comprehension is little affected by the vast variety of ways in which a single phrase can be uttered. This amazing ability to extract relevant information from wildly varying sensory signals is also ubiquitous in other sensory modalities, and is by no means restricted only to human speech. Even though the effect itself is well characterized, we do not understand the approaches used by different neural systems to achieve such performance. In an ongoing project, we are testing the hypothesis that broadly invariant signal processing is achieved through various combinations of locally invariant elements. The main questions we would like to address are: 1. What are the characteristics of locallyinvariant units in auditory pathways? 2. How are biological locallyinvariant units combined to form globally invariant processors? 3. What are the appropriate mathematical structures with which to address and model these sensory processes? The mathematical aspects of the research involve an interesting combination of probability theory (a must in the study of biological sensory systems) and group theory, needed to characterize invariants and symmetries. The combination defines the concepts of a probabilistic symmetry, and expands the scope of probabilities on group structures, originally introduced by Grenander. 
Nov 24  Thanksgiving 
Dec 1  Inverse problems: when what we measure is not what we want Doug Nychka, National Center for Atmospheric Research Location: Psychology 105 What will the weather be like tomorrow? What is the density of the Sun's atmosphere? How much carbon dioxide was in the atmosphere 500 years ago? Answers to these questions rely on using measurements that are not direct observations of the quantities of interest – a common problem in science and engineering. A powerful way to solve these problems is to formulate a statistical model that relates the unknown variables to what we observe and then find the solution that is most likely given the observations at hand. As a specific example this lecture will explain how to reconstruct the annual record of CO2 in the atmosphere from an Antarctic ice core. An important result of this analysis is not only being able to estimate these concentrations but also attach error estimates to them. This example also serves as a gentle introduction to Bayesian hierarchical models and their connection with regularization for solving mathematical inverse problems. 
Spring
4:405:30pm in P123 (unless marked otherwise). Directions to Reed.
Jan 26  Equivocating Yao: ConstantRounds Adaptively Secure Multiparty Computation in the Plain Model Muthuramakrishnan Venkitasubramaniam, Department of Computer Science, University of Rochester Yao’s circuit garbling scheme is one of the basic building blocks of crytographic protocol design. Originally designed to enable twomessage, twoparty secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds? We provide a positive answer to this question. We define a new type of encryption, called functionally equivocal encryption (FEE), and show that when Yao’s scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function. Combining our scheme with noncommitting encryption, we obtain the first twomessage, twoparty computation protocol, and the first constantrounds multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. We also provide extensions to the multiparty setting (with UCsecurity) and applications to leakage resilience. 

Feb 2  TBA Mark Sapir, Department of Mathematics, Vanderbilt University 
Feb 9  TBA Katherine McLaughlin, Statistics Department, Oregon State University 
Feb 16  TBA Mihai Tohaneanu , Department of Mathematics, University of Kentucky 
Feb 23  TBA Anurag Singh, Department of Mathematics, University of Utah 
Mar 2  TBA Aishwarya Thiruvengadam, University of Maryland, Department of Computer Science 
Mar 9  TBA Lyudmila Korobenko, UPenn/Reed College 
Mar 16  Spring break 
Mar 23  TBA David ZureickBrown, Department of Mathematics and Computer Science, Emory University 
Mar 30  TBA David Ayala, Montana State University 
Apr 6  TBA 
Apr 13  TBA Richard Moy, Department of Mathematics, Willamette University 
Apr 20  TBA Jayadev Athreya, Director Washington Experimental Mathematics Lab, Department of Mathematics, University of Washington 
Apr 27  TBA Clark Barwick, Department of Mathematics, MIT 