The MathAcrossCampus colloquium series consists of one main talk per quarter followed by a reception. Talks are open to the public and are intended to be accessible to a wide audience.

The primary goal of this lecture series is to expose students and researchers to a wide variety of applications of mathematics to real-world problems, with a special emphasis on the growing role of discrete methods.

David Shmoys, Cornell University

Irit Dinur (short biography), The Weizmann Institute of Science

Sometimes you just don't have enough time to read an entire proof, a brief scan is all you can afford. Probabilistically checkable proofs (PCPs), discovered 25 years ago, guarantee that even a brief scan will find an error if there is one. A PCP proof is created by taking a regular proof and splitting it cleverly into fragments. The key is a theorem asserting that locally consistent fragments must be coming from a globally correct proof. We will describe this surprising local-to-global phenomenon and show a variety of implications from computational optimization all the way to secure cloud computing.

Taylor Perron (short biography) , Massachusetts Institute of Technology

River networks, which branch like tree limbs across the landscape, are one of Earth’s most widespread and recognizable surface features. They have also been discovered on two other Solar System bodies, Mars and Saturn’s moon Titan. What do these striking landscape patterns tell us about the histories of alien worlds? I will show how mathematical and computational descriptions of slow-acting geological processes, combined with measurements of today’s landscapes, have provided a new perspective on the origin and evolution of river networks. I will then direct your gaze to Titan, where an exotic cocktail of materials and conditions has formed a deceptively Earth-like landscape, and show what our Earthly knowledge can teach us about this mysterious world.

Russ Tedrake (short biography) , Massachusetts Institute of Technology

The last few years have seen absolutely incredible advances in the field of robotics, with massive new investments from major companies including Google, Apple, and Uber. At the heart of these advances are algorithms, often using mathematical optimization, which allow our machines to better interpret massive streams of incoming data, to decide how and where to move, and even to balance and not fall down while they are executing those plans. In this talk, I'll describe some of those advances in the context of a controlling a 400lb humanoid robot in a disaster response scenario and an airplane that can dart through a forest at 30 mph. And I'd like to send a clear message -- there is still a lot of work to be done! Even small improvements in our mathematical foundations, such as the algorithms which check if a polynomial is uniformly greater than zero, can make our robots more capable of moving through the world.

Jeannette Wing (short biography) , Microsoft Research

Computational thinking is destined to be a fundamental skill taught to every child along with reading, writing, and arithmetic. Computational thinking involves solving problems, designing systems, and understanding human behavior by drawing on concepts that are fundamental to computer science. I will give examples of how computational thinking has already influenced many disciplines, from the sciences to the arts, and how it is transforming K-12 education. Computational thinking can not only inspire future generations to enter the field of computer science—it can benefit people in all fields.

This talk is co-sponsored by the Department of Computer Science & Engineering.

Dave Kung (short biography) , St. Mary's College of Maryland

The two subjects of math and music are connected in myriad ways, from the rhythm of notes to the frequencies of the pitches. At the advanced level, both mathematical theories and music theories help us understand the other subject. In this talk, we first explore what mathematics tells us about musical instruments, the basic tools of musical practice. In the second half, we flip sides, looking at music theory and how the structure of chords gives us another way to understand topological structures (circles, Möbius strips and higher dimensional tori), some of the basic tools of mathematical practice. Thus the first "movement" connects mathematical theory to musical practice, and the second "movement" connects musical theory to mathematical practice. Throughout, examples played on the violin will illustrate all of these beautiful and surprising connections.

Dan Spielman (short biography) , Yale University (Computer Science)

We will show how physical metaphors can help us understand the structure of a graph. The graphs arising in different disciplines can have very different characteristics: social networks, protein-protein interactions networks, road networks, and scientific meshes are all graphs. But, they can look very different from each other. This diversity makes it difficult to understand arbitrary graphs.

We will explore an approach to understanding graphs that has been unreasonably successful: imagining that a graph represents a phyisical object. For example, we may pretend that the edges of a graph are springs, rubber bands, or resistors. Linear algebraic techniques for understanding these physical systems naturally lead to the development of spectral and algebraic graph theory. We will survey some of the fundamental ideas from these fields.

Maryam Fazel (short biography) , University of Washington (Electrical Engineering)

What do a biomedical engineer aiming to speed up MRI scans, and a bookseller aiming to recommend books to readers have in common? Both can benefit dramatically from low dimensional structures and sparsity in their underlying models. Compressed sensing, which exploits sparsity , has revolutionized signal processing and medical imaging. Low-rank matrix estimation is at the heart of the recommendation problem and other modern data analysis tasks. This talk draws a mathematical connection between these seemingly disjoint problems and several others, and shows how sparsity and structure can be exploited to recover signals and models from very limited information.

Simon Levin (short biography) , Princeton University (Biology)

The continual increase in the human population and our demands on the Earth's limited resources, raises the urgent mandate of understanding the degree to which our actions are sustainable. This is an enormous scientific challenge and mathematics provides a common language to meet this challenge across disciplines. Mathematical tools help in understanding the collective dynamics of systems from bacterial biofilms to bird flocks and fish schools to ecosystems and the biosphere. They also provide ways to resolve the game-theoretic challenges of achieving cooperation among individuals and among nations in providing for our common future.

Richard Tapia (short biography) Rice University (Computational and Applied Mathematics)

In this talk the speaker will identify elementary mathematical frameworks for the study of old and new drag racing beliefs. In this manner some myths are validated, while others are destroyed. The first part of the talk will be a historical account of the development of drag racing and will include several lively videos and pictures depicting the speaker's involvement in the early days of the sport.

Tom Daniel (short biography), University of Washington (Biology)

Muscle is nature's most versatile machine. Converting chemical energy into mechanical work, muscle can act as an actuator, a brake, or even a spring. In collaboration with undergraduates, graduate students and postdocs, we have focused on understanding how billions of molecular motors can interact to drive motion in animals. We have used everything from simple algebra to cloud computing to calculate and predict how forces are generated.

Adrienne Fairhall, (short biography) University of Washington (Physiology and Biophysics)

The brain is often thought of as a computer, taking in and transforming information into new forms that allow it to drive actions. How does one mathematically quantify how information is represented in neural systems? We show that in many sensory systems, information is represented efficiently, even at the level of single neurons, and that properties of single neurons can dramatically affect the way in which information at different timescales is propagated through neural networks.

Don Saari (short biography) , University of California, Irvine (Mathematics, Economics)

It happens so often: In some election it is debatable whether the "winner" is who the voters really wanted. But the "winner" can affect the future of an organization, whether a fraternity, sorority, academic department, city, county, state, or country, so consequences can be serious. As described in this expository lecture, the power of mathematics is making it possible to identify the persistent villains that can lead us astray – our choice of voting rules. Because some of the nastier rules are so commonly used, audience members may leave legitimately worried about the accuracy of a recent election outcome.

David Baker (short biography) , University of Washington (Biochemistry)

The elementary processes of life are carried out by proteins. Proteins are very large molecules with thousands of atoms and many hundreds of degrees of freedom and hence have a vast number (~3^100) of possible conformations. Despite this diversity, proteins fold to single unique states which allow them to carry out their functions. Each protein has a unique amino acid sequence, and the folded structure of a protein is the lowest energy conformation for its amino acid sequence. I will discuss progress in predicting the structure of proteins from their amino acid sequences and in designing new proteins to address 21st century challenges. Both prediction and design are global optimization problems--the prediction problem is to find the lowest energy conformation for a given amino acid sequence, and the design problem, to find the lowest energy sequence for a desired structure or function. I will also describe how the general public has contributed to solving these global optimization problems through the distributed computing project Rosetta@Home and the online game FoldIt.

Margaret Wright (short biography) , Courant Institute of Mathematical Sciences, New York University (Computer Science)

Linear programming (LP), which isn't really about programming, is a simple-to-state mathematical problem of enormous practical importance. The dramatic saga of LP solution methods began immediately after World War II with unexpected practical success that continued for more than 30 years despite theoretical reservations; next came two sweeping revolutions whose effects are still widely misunderstood. This talk will describe mathematical and computational issues from the history of LP, enlivened by controversy and international politics, as well as some fascinating remaining mysteries.

John Lowengrub, (short biography) University of California, Irvine (Mathematics, Biomedical Engineering, Chemical Engineering & Materials Science)

Cancer is fundamentally a loss of control in a complex biological system, as the tightly regulated rate of cell division breaks down. In this talk, we demonstrate how an interdisciplinary approach synthesizing developmental biology, engineering feedback control, and mathematical modeling can help to determine the control processes operating within an individual tumor. Such information can both provide insight into how different types of tumors develop, as well as patient-specific prognosis of the effects of therapy.

Elizabeth Thompson (short biography), University of Washington (Statistics)

Is this my cousin? How much of our genomes do we share? How long are the segments of chromosome we share? Is a trait we share genetic? Do we share the segment of genome that predisposes us to this trait? The outcomes of the complex biological process of meiosis have deceptively simple probability laws, but the patterns of genome shared identical-by-descent (ibd) are complex. The ibd-graph summarizes shared genome. Modern genome-wide genetic marker data permit inference of the genome-wide ibd-graph. This talk will show us how these inferences can assist us in answering these questions.

Peter Winkler (short biography), Dartmouth College (Mathematics, Computer Science)

Valuable as mathematics is, 99.99% of our daily decisions are based on intuition — but this intuition is in turn based on mathematics. Estimating sizes, times, and probabilities, and then working tacitly with these estimates, is the stuff of life. Mathematical puzzles are a way to help keep our intuition from running off the rails. Several puzzles, some with solutions and some without, will be presented as illustrations. Hopefully, your intuition will never be quite the same again!

Nick Trefethen (short biography), Oxford University (Numerical Analysis)

Suppose four bugs at the corners of a 2 x 1 rectangle start chasing each other at speed 1. Bug 1 chases bug 2, bug 2 chases bug 3, and so on. What happens next will amaze you. As we follow the bugs to their eventual collision at the center, we will encounter the biggest numbers you've probably ever seen and confront some fundamental questions about what it means to try to understand our world through mathematics.

Professor Trefethen is the Math department's Milliman Speaker for 2010, and will be giving two more talks on April 14th and 15th, at 4pm in Savery Hall 260.

Roger Myerson (short biography), University of Chicago (Economics)

Democratic political liberalization depends on incentives for the ruling elite. Even a popular revolution could not create sustained democracy if any leader, once installed in power, would act to make himself an authoritarian ruler. This talk considers a simple political-economic model where capitalist investment is constrained by the government's temptation to expropriate. We use this to show how fundamental economic forces can motivate a ruler to liberalize his regime, even though such liberalization increases his political risks and shortens his expected term of office.

Greg Hakim (short biography), University of Washington (Atmospheric Sciences)

The use of observations and models to predict the future state of a system is a hallmark of the scientific method that often has practical application. As a result, estimation and prediction are central pursuits across a vast range of disciplines, including the physical, biological, and social sciences; engineering; and finance. In many cases the system of interest is composed of a large number of interacting components that render estimation and prediction difficult. This challenge motivates this talk in which I will review essential aspects of, and the basic theory for, estimating and predicting complex systems. One such system, Earth's atmosphere, will be used to illustrate techniques that deal with complexity. The success of these methods for reducing uncertainty in weather forecasts will be contrasted against a failure to reduce uncertainty in climate-change forecasts. This contrast motivates a mathematically based reconsideration of model formulation and calibration for complex systems.

Andrew Gelman (short biography), Columbia University (Statistics, Political Science)

We shall consider two topics involving coalitions and voting. Each topic involves open questions both in mathematics (probability theory) and in political science.

- Individuals in a committee or election can increase their voting power by forming coalitions. This behavior yields a prisoner's dilemma, in which a subset of voters can increase their power, while reducing average voting power for the electorate as a whole. This is an unusual form of the prisoner's dilemma in that cooperation is the selfish act that hurts the larger group. The result should be an ever-changing pattern of coalitions, thus implying a potential theoretical explanation for political instability.
- In an electoral system with fixed coalition structure (such as the U.S. Electoral College, the United Nations, or the European Union), people in diferent states will have different voting power. We discuss some flawed models for voting power that have been used in the past, and consider the challenges of setting up more reasonable mathematical models involving stochastic processes on trees or networks.

Here are some research articles related to Professor Gelman's talk:

- Forming Voting Blocs and Coalitions as a Prisoner's Dilemma: A Possible Theoretical Explanation for Political Instability by Andrew Gelman
- The Mathematics and Statistics of Voting Power by Andrew Gelman, Jonathan N. Katz, and Francis Tuerlinckx
- Standard Voting Power Indexes Do Not Work: An Empirical Analysis by Andrew Gelman, Jonathan N. Katz, and Joseph Bafumi

Professor Gelman will also be speaking **Friday, June 5, 2009**, 9:45 – 11:00am in Kane Hall 225 for the Conference on Statistics and the Social Sciences at the University of Washington.

There will be no brown bag discussion with Professor Gelman.

Martin Grötschel (short biography), Technische Universität Berlin & ZIB (Information Technology)

Slides from presentation (.pdf) (.ppt)

Prof. Grötschel's course on combinatorial optimization at TU Berlin (Sep 21 – Oct 9, 2009)

Combinatorial optimization exploded on the mathematical and scientific scene in the 1950s. In this lecture I will briefly survey its development for a wide audience. Theoretical design and analysis of algorithms dominated the early development of the field, while computational progress has been particularly significant in the last twenty years. These theoretical and computational achievements, combined with successful modeling of applications, have made it possible today to solve real-world problems of breathtaking size and diversity. The majority of the lecture will report on success stories in areas such as telecommunication, transportation, traffic and logistics. These results are based on ongoing cooperation between industry, the DFG Research Center MATHEON and my research group at Konrad-Zuse-Zentrum (ZIB).

**Brown bag discussion session** with Martin Grötschel:

Friday, January 23, 2009, 12:30 – 2:20pm in Smith Hall 115

Joe Felsenstein (short biography), University of Washington (Genome Sciences, Biology)

An evolutionary tree (a phylogeny) is a graph that shows the sequence of speciation events where one species splits into two. Two other types of tree have also become common in studies of molecular evolution. Coalescents are trees of copies of genes within a single species, and trees of gene duplication show the origin of new genes from old ones. All these trees are interrelated, and they "live" in unusual and difficult spaces. Although biologists now understand that we need mathematics and statistics to think clearly about inferring these trees, mathematics has as yet contributed few important insights about them.

**Brown bag discussion session** with Joe Felsenstein:

Friday, November 14, 2008, 12:30 – 1:20pm in Miller Hall 302A

Invitees are high level researchers who are also renowned public speakers, selected by the MathAcrossCampus community. Ideally, one of the three annual speakers is chosen from within the Seattle community. The subject areas are kept as diverse as possible, and the main talk is intended to be accessible to a wide audience. Nominations of speakers are open to all; if you would like to nominate a speaker, send email to
[*enable JavaScript to view email address, or contact the organizers directly*]
.