Fall 2015

Mondays, 5pm-6pm, 891 Evans Hall

Dinner afterwards

The Applied Algebra Seminar is an interdisciplinary seminar on applications of algebra to fields outside mathematics. Our goal is to connect mathematicians with researchers from other fields using algebraic tools in their work.

Talks are aimed at an interdisciplinary graduate student audience including mathematicians, computer scientists, engineers, biologists, economists, statisticians, and more.

Mailing List

Please sign up for the seminar mailing list to receive information about applied algebra happenings around campus. You can also contact the organizers to be added to the mailing list.

Organizers

Please contact David Dynerman or Elina Robeva if you are interested in giving a talk! Both mathematicians and scientists in other fields are warmly invited to present.

 

Upcoming Speakers

November 30 — Mariann Ollar, University of Pennsylvania (Economics)

Mariann Ollar

Polynomial Equations Arising from Divisible Good Auctions

In financial exchanges and auctions, the information that traders use to decide how to act exhibits various interdependencies as a result of shared information sources or central forecasting agencies. Market clearing auctions are auctions that allow for the division of goods across multiple winners at a price determined by the auction.

Models of market clearing auctions give rise to a system of polynomial equations, and the solutions of this system correspond to equilibrium strategies for the traders. In the special case where each trader's information relates to the market in the same way, this system has a unique closed form solution. However, in the general case this system exhibits multiple solutions. The algebraic properties of these polynomial systems and newly developed software tools (Bertini) help us identify the extent of this multiplicity, which has implications for information aggregation and trade efficiency.

December 7 — David Dynerman, UC-Berkeley (Math)

Elina Robeva

Studying continuous conformational changes of proteins using cryo-EM

Proteins are the workhorses that underlie the vast majority of function in living organisms. Many proteins operate as molecular machines, meaning that they perform their task by mechanical means. For instance, a ratcheting motion of the ribosome advances incoming genetic code as it works to translate RNA into new proteins. Because of this, discovering a 3D structure (also called a conformation) of a protein, and understanding how these conformations change, is an important part of understanding how proteins work.

Cryo-electron microscopy (cryo-EM) is a laboratory technique used to discover 3D structures of proteins. Cryo-EM experiments take a sample containing many copies of a protein and produce a large number of very noisy 2D images that can be used recover a 3D model. An important advantage of cryo-EM is that it does not require the sample to be crystallized, as with X-ray crystallography. This can be a very difficult task, and we are not able to crystallize many important biological molecules that we would like to study.

The primary difficulty encountered in cryo-EM experiments is the large amount of noise in the 2D images that are produced. When the sample only contains a single conformation of the protein, information from many images can be combined to overcome noise and produce a high quality 3D reconstruction. These methods can also be applied if the sample contains a handful of sharply distinguished conformations. However, this approach fails if the sample contains proteins with continuous conformational changes, such as the ratcheting motion of the ribosome.

In this talk, we will first give an overview of how cryo-EM works and why current algorithms struggle with continuous conformations. Then we will present a proposed new algorithm for cryo-EM, due to Dashti et al., that uses ideas from differential geometry to attempt to reconstruct not just a single 3D structure, but the entire range of conformational changes present in a sample.

 

Past Speakers

September 2 — Tom Melia, UC-Berkeley (Physics)

Tom Melia

Hilbert series and operator bases in effective field theories

Effective field theories (EFTs) are ubiquitous throughout physics, having application in particle physics, condensed matter, hydrodynamics, etc.. An important problem is determining which operators appearing in the Lagrangian of an EFT are independent (i.e. do not give rise to the same physical effect).

I will discuss a new, systematic approach to counting independent operators in an EFT which translates this problem into understanding the Hilbert series of a polynomial ring. In a simple 1d EFT of \(N\) real scalar fields, the ring is a specific case of a Cox-Nagata ring. I will define a generalized Hilbert series for this theory, explore the analytic structure of this object, and make a connection with Molien's formula as applied to an underlying \(\text{SL}(2,\mathbb{C})\) structure in the theory.

September 21 - Martin Helmer, UC-Berkeley (Math)

Martin Helmer

Algorithms to Compute Topological Invariants of Subschemes of Smooth Toric Varieties

Topological invariants are an important tool to aid in understanding and categorizing the structure and properties of algebraic varieties. Besides being of interest for problems in mathematics such invariants have also been applied to problems from string theory in physics and to problems of maximum likelihood estimation in statistics. In this talk we discuss methods to compute several common topological invariant of some toric varieties.

More specifically we will discuss and demonstrate probabilistic algorithms to compute the Segre class, Chern class, Chern-Schwartz-MacPherson class and Euler characteristic of subschemes (or subvarieties) of a class of smooth toric varieties which include products of projective spaces.

To construct these algorithms we prove a new expression for the Segre class of a subscheme of some such toric varieties which is both explicit and computable. Implementations of the algorithms are tested and found to offer significantly increased performance over other known algorithms; running time bounds are also given. In the case of the Chern-Schwartz-MacPherson class this is algorithm is the first algorithm known to us which is applicable in this setting.

The algorithms presented may be implemented using both symbolic (i.e. Groebner basis) and numeric (i.e. homotopy continuation) methods. Our test implementation is available as a Macaulay2 package.

September 28 — Anna Seigal, UC-Berkeley (Math)

Anna Seigal

An algebraic tensor approach to clustering breast cancer cell lines

Cancer cells respond to the signaling molecules they encounter in different ways, and these differences play an important role in predicting tumor development and drug response. Breast cancer cell lines are traditionally divided into three subtypes, but the existing classification is not a good predictor of the response to signaling molecules.

Here, we develop a tensor method that yields a finer classification of the cell lines. Our results motivate the construction of cluster-specific mechanistic models to describe the relation of two main communication pathways in breast cancer. In this talk, I will describe the mathematics behind the tensor method.

This is based on joint work with Heather Harrington at the University of Oxford.

October 5 — Danny Crow, UW-Madison (Physics)

Danny Crow

Using Algebraic Geometry to Study Entanglement in Quantum Computers

Entanglement has long been one of the most puzzling aspects of quantum mechanics. Despite being poorly understood, it is generally accepted that entanglement will play a crucial role in building a quantum computer.

To better understand the effect entanglement has on computation, physicists seek a way to determine the amount of entanglement in a quantum computer as an algorithm executes. However, in all but the simplest cases, it is difficult to determine whether or not entanglement is even present.

In this talk we will begin by showing how quantum computers work, and explaining what entanglement is and why physicists believe it is so important. Then, we will provide a geometric description of quantum states in terms of the convex cone of positive semi-definite matrices, and show how this description allows us to approximate the set of entangled quantum data.

This talk is aimed at graduate students from physics, math, CS and beyond. We hope that every audience member will learn something interesting from our talk.

This project is joint with David Dynerman.

October 19 — Daniel Pimentel, UW-Madison (Electrical Engineering)

Daniel Pimental

On Subspaces and Missing Data

We love subspaces. We observe a phenomenon and try to find a line that explains it. Sometimes one line is not enough. Data are often better explained by multiple lines, or more generally, unions of subspaces.

In many relevant applications, missing data are common. Yet we are not going to let that stop us. We still want to find the subspaces that best explain incomplete datasets. In this talk I will discuss the difficulties of this task, and present our algebraic approach to answer the following fundamental question: how incomplete can a dataset be, such that we can still identify its underlying subspaces? Or equivalently, how incomplete can a set of vectors be, such that they still uniquely define a subspace (just as a set of complete, linearly independent vectors would)?

Our results also shed new light on the popular low-rank matrix completion problem (the particular case when there is only one subspace).

November 4 - Applied Algebra Minisymposium, 1pm-4pm, 732 Evans

Note special time and place.

 

1pm - 145pm: Extending Persistent Homology: Zigzags and Well Groups

Dmitriy Morozov

Dmitriy Morozov, Lawrence Berkeley National Lab

This talk will describe two extensions to persistent homology, zigzag persistent homology and well groups, and how all three relate to each other, through a Mayer--Vietoris pyramid, when the input data is a real-valued function.

2pm - 245pm: Topological data analysis for investigation of dynamics and networks

Heather A. Harrington

Heather A. Harrington, Oxford (Math)

Persistent homology (PH) is a technique in topological data analysis that allows one to examine features in data across multiple scales in a robust and mathematically principled manner, and it is being applied to an increasingly diverse set of applications. We investigate applications of PH to dynamics and networks, focusing on two settings: dynamics {em on} a network and dynamics {em of} a network.

Dynamics on a network: a contagion spreading on a network is influenced by the spatial embeddedness of the network. In modern day, contagions can spread as a wave and through the appearance of new clusters via long-range edges, such as international flights. We study contagions by constructing ‘contagion maps’ that use multiple contagions on a network to map the nodes as a point cloud. By analyzing the topology, geometry, and dimensionality of manifold structure in such point clouds, we reveal insights to aid in the modelling, forecast, and control of spreading processes.

Dynamics of a network: one can construct static graph snapshots to represent a network that changes in time (e.g. edges are added/removed). We show that partitionings of a network of random-graph ensembles into snapshots using existing methods often lack meaningful temporal structure that corresponds to features of the underlying system. We apply persistent homology to track the topology of a network over time and distinguish important temporal features from trivial ones. We define two types of topological spaces derived from temporal networks and use persistent homology to generate a temporal profile for a network. We show that the methods we apply from computational topology can distinguish temporal distributions and provide a high-level summary of temporal structure.

Together, these two investigations illustrate that persistent homology can be very illuminating in the study of networks and their applications.

3pm - 345pm: The phylogenetic operad

Nina Otter

Nina Otter, Oxford (Math)

Phylogenetics is concerned with the study of evolutionary relationships among species or genes. These relationships are usually represented by metric trees called phylogenetic trees. Billera, Holmes and Vogtmann introduced a space that parametrizes the set of all phylogenetic trees with a fixed set of leaves. A lot of research has been done to understand the combinatorics and geometry of this space to develop suitable statistical methods. In this talk I will present recent work that relates the space of phylogenetic trees to a certain operad, which we call the phylogenetic operad. I will first introduce the space of phylogenetic trees, and talk about some of its combinatorial and geometric properties. Then I will give a very gentle introduction to operads and describe two results: the space of phylogenetic trees with n leaves is homeomorphic to the space of n-ary operations of the phylogenetic operad, and Markov processes used in phylogenetics give coalgebras over this operad. This talk is based on joint work with John Baez.

November 9 - Joe Kileel, UC-Berkeley (Math)

Joe Kileel

A Chow Form in Computer Vision

In computer vision, 3D reconstruction is a fundamental task: starting from photographs of a world scene, taken by cameras in unknown positions, create a 3D model of that world scene. Algorithms for this are used in Street View (Google Maps) and are embedded in every smart phone. In this talk, we will introduce and answer a basic mathematical problem when the number of cameras is two, left open by Googler Agarwal and his co-authors.

The answer is a determinantal formula for the Chow form of the configuration space of two calibrated cameras, which is a five-dimensional variety in \(\mathbb{P}^8\). It is in the spirit of classical Bézoutian formulas for resultants, but we need representations of \(\text{GL}_4\) and the modern theory of Ulrich sheaves to derive it. I will show some examples from numerical linear algebra to illustrate the utility of the result.

I will walk a tight rope and keep this talk accessible to graduate students in math and EECS alike. Joint with Gunnar Fløystad and Giorgio Ottaviani.