The SPAMS Schedule - Fall 2017

Abstract: In 1999 Terry Tao and Allen Knutson built on work of Klyachko and others to prove the so-called Saturation Conjecture for Littlewood-Richardson coefficients, and thereby Horn's conjecture on possible spectra of sums of Hermitian matrices. We will discuss the ideas behind this result and its implications for the computational complexity of the positivity question for Littlewood-Richardson coefficients.

Abstract: Caratheodory's Theorem says that in R^d every point in a convex polytope can be written as the convex combinationof d + 1 vertices, which is tight. However if we only seek to be within an epsilon-ball of the point and the polytope has bounded diameter, it turns out O(1/epsilon^2) vertices suffice, with no dependence on d. We present two algorithmic proofs, one using probability and second a deterministic one using convex optimization. No background assumed.

Abstract: Elastic rods and spinning tops are two easily accessible systems which are fun to play with. Surprisingly, there is a mapping between the dynamics of a spinning top in time and the dynamics of a twisted elastic rod in space. We will use this dynamic analogy to find interesting behaviours in both systems.

Abstract: How should one estimate a signal, given only access to noisy versions of the signal corrupted by unknown circular shifts? This simple problem has surprisingly broad applications, in fields from structural biology to aircraft radar imaging. We describe how this model can be viewed as a multivariate Gaussian mixture model whose centers belong to an orbit of a group of orthogonal transformations. This enables us to derive matching lower and upper bounds for the optimal rate of statistical estimation for the underlying signal. These bounds show a striking dependence on the signal-to-noise ratio of the problem. (Joint with Afonso Bandeira and Philippe Rigollet.)

Abstract: Metagenomics is the study of environmental DNA from interesting environments, most importantly the human gut. One of the first things that need to be done when analyzing metagenomic datasets is binning, whereby reads are assigned to the species they belong to. While this can be done for species whose reference genomes we know, a significant number of reads come from novel species whose genomes have not been sequenced. A key challenge of clustering these reads is that we have no idea how many clusters we are looking for. The Dirichlet process prior from Bayesian nonparametrics offers a flexible solution by providing a generative model that allows for an unbounded number of clusters.

Abstract: In the ocean, some animals use small scale surface variations to induce macro-scale flow characteristics in the surrounding water. In particular, crustaceans have chemosensory hairs on their antenna that they use to detect odors and track their food. Biologists have discovered that crustaceans also use the hairs to manipulate flow and increase the effectiveness of chemo-sensing. In this talk, we discuss the mechanics of flow around hairs. Because modeling the flow through an intricate geometry is computationally difficult, we will discuss the benefits and limitations of different approximations for modeling a rigid hair.

Abstract: Frame structures, which are made by connecting spatial nodes in space with straight elements, have been widely used in many fields, such as architecture and geometric modeling. An interest in robotic fabrication and construction of frame structures has been increasingly growing in recent years. To enable robots to fabricate complex frame structures, feasible construction sequence needs to be solved. Divide-and-conquer strategy offers a solution to alleviate the computation cost of sequence searching. In this talk, we present an iterative constrained graph cut algorithm to decompose the structure into subgroups and a heuristic searching algorithm to perform efficient construction sequence searching in each subgroup.

Abstract: During pregnancy, oxygen diffuses from maternal to fetal blood through placental tissue. A multi-scale model of the human placenta will require the simulation of blood flow and oxygen transfer in large feto-placental capillary networks. In this work, a model is described which allows such simulations to be performed. Realistic hemodynamic effects such as plasma skimming are taken into account and oxygen transfer is calculated by treating capillaries as modified Krogh cylinders. Two main uses of the model are illustrated. First, the effect of network structure and hematocrit on fetal oxygen supply are investigated. Second, simulations are performed on realistic geometries, generating results to be coupled to simulations of flow and oxygen transfer in larger vessels in future multi-scale simulations.

Abstract: In the planted clique problem, given an $n$-vertex Erdos-Renyi random graph with a clique added on $k$ vertices, the task is to efficiently recover the clique. This model was introduced by Alon, Krivelevich and Sudakov in 1997 and has since been shown to be solvable by a variety of algorithms. However, all known polynomial-time algorithms cease to work when $k = o(\sqrt{n})$. Recently, the assumption that planted clique is hard when $k = o(\sqrt{n})$ has been used to show tight lower bounds in machine learning and security in cryptography. In this talk, we will survey the different algorithms recovering the clique when $k = \Omega(\sqrt{n})$ including the spectral algorithm, the SDP and an iterative degree thresholding algorithm.

Abstract: We will talk about Alan Turing's most cited paper, "The Chemical Basis of Morphogenesis", one of the most fundamental works in pattern formation. In this paper, Turing suggested a mathematical model to explain how a growing embryo breaks its spatial symmetry. More specifically, Turing argued that a system of morphogens (chemical substances), reacting together and diffusing through a tissue, could develop a pattern from a uniform initial state without any specific external interference.

Abstract: When is a crystal electrically insulating? Viewing electrons as particles, we expect a system to be insulating precisely when all the electrons are pinned to some local potential minima in space. Electrons, however, are also quantum-mechanical waves. In the wave picture, insulators arise from delicate destructive interference effects that inhibit the transport of charges. Curiously, these two pictures do not generally agree, and a “wave-like insulator” which is not “particle-like” is inherently quantum mechanical in nature. Such systems are more formally called “topological insulators,” and they display intriguing physical properties like a necessarily conductive surface even when the bulk is completely insulating. In this talk, I will describe how such exotic phases of matter can be efficiently discovered using spatial symmetries — a defining feature of any crystal. This is achieved through the use of elementary group theory, like representations and quotients, which greatly simplifies the analysis and allows us to obtain exhaustive results for all 1,651 magnetic space groups.