The SPAMS Schedule - Spring 2018

Abstract: Complex real-world phenomena across a wide range of scales, from aviation and internet traffic to signal propagation in electronic and gene regulatory circuits, can be efficiently described through dynamic network models. In many such systems, the spectrum of the underlying graph Laplacian plays a key role in controlling the matter or information flow. To complement the traditional procedure of constructing graph ensembles with predefined statistical adjacency characteristics, I will present a mathematically rigorous weighted graph construction that exactly realizes any desired spectrum. I will then illustrate the broad applicability of this approach by showing how gapped spectra can be used to control the dynamics of various archetypal physical systems, in particular inducing chimera states in Kuramoto-type oscillator networks, controlling pattern formation in a generic Swift-Hohenberg model, and causing persistent localization in a discrete Gross-Pitaevskii quantum network. The construction can be generalized to design continuous band gaps through periodic extensions of finite networks.

Abstract: Imagine we want to recover an unknown vector given many noisy copies of it, except each copy is cyclically shifted by an unknown offset. Or imagine we want to reconstruct an unknown 3D structure (e.g. a molecule) given many noisy pictures of it taken from different unknown angles. These problems (and many others) belong to the class of "orbit recovery" problems wherein we observe many noisy copies of an unknown vector, each acted upon by a random element of some compact group. I'll talk about how to solve such problems with optimal sample complexity using the method of moments. This will involve some tools from algebraic geometry and invariant theory (but I will not assume knowledge of these). Based on joint work with Afonso Bandeira, Ben Blum-Smith, Amelia Perry, and Jon Weed (https://arxiv.org/abs/1712.10163).

Abstract: Fracture plays a crucial role in physical and biological processes across a range of length scales. However, fracture control continues to present profound practical and theoretical challenges. A famous longstanding problem posed by Feynman asks why brittle elastic rods appear almost always to fragment into at least three pieces when placed under large bending stresses. Feynman’s observation raises fundamental questions about the existence of protocols that can robustly induce binary fracture in brittle materials. Using experiments, simulations and analytical scaling arguments, we demonstrate controlled binary fracture of brittle elastic rods for two distinct protocols based on twisting and quenching. Due to their generality, these results are expected to be widely applicable.

Abstract: I will describe what the mean field approximation is for an Ising model. Then I will explain some examples and facts about it. Related to joint work with Vishesh Jain and Elchanan Mossel.

Abstract: A 1-factorization of a graph G is a partitioning of its edges into perfect matchings. It is clear that if a graph G admits a 1-factorization, then it must be regular; the converse is easily seen to be false.

I will survey known results/conjectures regarding the existence and the number of 1-factorizations in graphs, and present new results which settle some of these conjectures. This is based on joint work with Asaf Ferber (MIT) and Benny Sudakov (ETH Zurich).

Abstract: Suppose you are given a \sqrt(n) x \sqrt(n) grid and n (potentially overlapping, not necessarily connected) regions of arbitrary size. Your goal is to color the points red and blue such that all regions have nearly the same number of red and blue points. Spencer's classic "six standard deviations suffice" result tells you that there is a coloring so that for all regions R, the quantity |# red points in R - # blue points in R| is no larger than 6*\sqrt(n). His approach was an ingenious application of the probabilistic method via Shannon entropy. I will explain the key steps in the proof of this result and describe (with no proofs) a relatively recent, simple algorithm due to Lovett and Meka that achieves Spencer's bound up to a constant factor.

Abstract: Quantum (random) walks are natural generalizations of classical random walks to a quantum-mechanical setting. It turns out that there are many such natural ways to carry out this generalization mathematically. In this talk, I’ll focus on a few canonical definitions of the discrete-time quantum walks and discuss some of their uniquely quantum behaviors. I will highlight how these behaviors can be leveraged to achieve quantum speed-up in the context of search algorithms. Although officially coined in the literature in the early 1990s by Aharonov et al, the discrete-time quantum walk was actually introduced by Feynman in the textbook “Quantum Mechanics and Path Integrals” as a discretized space-time model for the Dirac equation. In fact, many authors have (non-rigorously) shown that the continuum limit of the evolution of certain discrete-time quantum walks is the Dirac equation. This provides a link between quantum algorithms and fermionic relativistic wave equations. I will conclude the talk with a list of reported results in the literature that explore this link and some speculations on future directions.

Abstract: Properties of image formats (e.g. raster vs vector, lossy vs lossless, compression, ...) determine their best use cases. We will discuss an unusual format: Diffusion Curves. Colour discontinuities in the image are stored, and the rest of the image is interpolated using the Laplace equation or biharmonic equation. There will be some discussion of the underlying mathematics, practical considerations, and examples.

Abstract: In the wild, the RSA cryptosystem needs "padding" to function. That is, instead of encrypting "Hello world", you encrypt e.g. "541n80m4389ft3 || Hello World". Unfortunately, if padding is implemented in a common subtly incorrect way, then RSA becomes vulnerable to a man-in-the-middle attack that uses some nice math. Time permitting, I'll talk about some other mathematical crypto vulnerabilities.