PACM Colloquium

Fall 2017

PACM Colloquium: Walking within growing domains: recurrence versus transience

Speaker: 
Amir Dembo, Stanford University
Date: 
Sep 18 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

When is simple random walk on growing in time d-dimensional domains recurrent? For domain growth which is independent of the walk, we review recent progress and related universality conjectures about a sharp recurrence versus transience criterion in terms of the growth rate. We compare this with the question of recurrence/transience for time varying conductance models, where Gaussian heat kernel estimates and evolving sets play an important role. 

We also briefly contrast such expected universality with examples of the rich behavior encountered when monotone interaction enforces the growth as a result of visits by the walk to the current domain's boundary.

This talk is based on joint works with Ruojun Huang, Vladas Sidoravicius and Tianyi Zheng.

PACM Colloquium: Polynomial Optimization and Dynamical Systems

Speaker: 
Amir Ali Ahmadi, Princeton University
Date: 
Sep 25 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

In recent years, there has been a surge of exciting research activity at the interface of optimization (in particular polynomial, semidefinite, and sum of squares optimization) and the theory of dynamical systems. In this talk, we focus on two of our current research directions that are at this interface. In part (i), we propose more scalable alternatives to sum of squares optimization and show how they impact verification problems in control and robotics. Our new algorithms do not rely on semidefinite programming, but instead use linear programming, or second-order cone programming, or are altogether free of optimization. In particular, we present the first Positivstellensatz that certifies infeasibility of a set of polynomial inequalities simply by multiplying certain fixed polynomials together and checking nonnegativity of the coefficients of the resulting product.

In part (ii), we introduce a new class of optimization problems whose constraints are imposed by trajectories of a dynamical system. As a concrete example, we consider the problem of optimizing a linear function over the set of initial conditions that forever remain inside a given polyhedron under the action of a linear, or a switched linear, dynamical system. We present a hierarchy of linear and semidefinite programs that respectively lower and upper bound the optimal value of such problems to arbitrary accuracy. 

Amir Ali Ahmadi ( http://aaa.princeton.edu/ ) is an Assistant Professor at the Department of Operations Research and Financial Engineering at Princeton University and an Associated Faculty member of the Department of Computer Science. Amir Ali received his PhD in EECS from MIT and was a Goldstine Fellow at the IBM Watson Research Center prior to joining Princeton. His research interests are in optimization theory, computational aspects of dynamics and control, and algorithms and complexity. Amir Ali's distinctions include the Sloan Fellowship in Computer Science, the NSF CAREER Award, the AFOSR Young Investigator Award, the DARPA Faculty Award, the Google Faculty Award, the Goldstine Fellowship of IBM Research, and the Oberwolfach Fellowship of the NSF. His undergraduate course at Princeton (ORF 363, ''Computing and Optimization’’) has received the 2017 Excellence in Teaching of Operations Research Award of the Institute for Industrial and Systems Engineers. Amir Ali is also the recipient of a number of best-paper awards, including the INFORMS Computing Society Prize (for best series of papers at the interface of operations research and computer science), the Best Conference Paper Award of the IEEE International Conference on Robotics and Automation, and the prize for one of two most outstanding papers published in the SIAM Journal on Control and Optimization in 2013-2015. 

PACM Colloquium: Trace reconstruction for the deletion channel

Speaker: 
Yuval Peres - Microsoft Research
Date: 
Oct 2 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

In the trace reconstruction problem, an unknown string $x$ of $n$ bits is observed through the deletion channel, which deletes each bit with some constant probability $q$, yielding a contracted string.  How many independent outputs (traces) of the deletion channel are needed to reconstruct $x$ with high probability?

The best lower bound known is linear in $n$.  Until recently, the best upper bound was exponential in the square root of $n$. We improve the square root to a cube root using statistics of individual output bits and some complex analysis;  this bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently and concurrently by De, O’Donnell and Servedio).  If the string $x$  is random and $q<1/2$, we can show a subpolynomial number of traces suffices by comparison to a biased random walk.   (Joint works with Fedor Nazarov, STOC 2017 and with Alex Zhai, FOCS 2017). In very recent work with Nina Holden and Robin Pemantle, we removed the restriction $q<1/2$ for random inputs.

Yuval Peres is a Principal Researcher at Microsoft Research in Redmond. He obtained his Ph.D. at the Hebrew University, Jerusalem in 1990, and later taught there and at the University of California, Berkeley. He has published more than 280 research papers and has co-authored books on Brownian motion, Markov chains, Probability on Networks, Fractals, and Game Theory. Yuval was awarded the Rollo Davidson Prize in 1995, the Loève Prize in 2001, and the David P. Robbins Prize in 2011. He was an invited speaker at the 2002 International Congress of Mathematicians, and a plenary lecturer at the Mathematics Congress of the Americas in 2017. He has advised 21 Ph.D. students. In 2016 he was elected as a foreign associate to the U.S. National Academy of Sciences.

PACM Colloquium: The reinvention of phase retrieval

Speaker: 
Veit Elser, Cornell University
Date: 
Oct 9 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

Phase retrieval, originally, was the idea of exploiting prior information in the reconstruction of a complex-valued signal when only its magnitude can be measured. The earliest and still most important application is the reconstruction of complex biomolecules from x-ray diffraction (magnitude) data taken from crystallized samples. Over the last few years, and in the applied math community, “phase retrieval” has become identified with a different problem: extending the reach of magnitude-only data by expanding the set of “sensing vectors” used to interrogate the signal, and the design of algorithms that in the new setting can promise a successful reconstruction. This reinvention of phase retrieval is disappointing in two respects. First, owing to the extreme smallness of the x-ray/molecule interaction, the proposal of designed sensing vectors — in the main application of structural biology — is physically unfeasible. Second, the new algorithms designed for the new phase retrieval problem do not offer, in practice, significant advantages over older algorithms developed for the original problem, even as these do not come with a guarantee of success.

PACM & CSML Joint Colloquium: Methods of network comparison

Speaker: 
Sofia Olhede, University College London
Date: 
Oct 16 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

The topology of any complex system is key to understanding its structure and function. Fundamentally, algebraic topology guarantees that any system represented by a network can be understood through its closed paths. The length of each path provides a notion of scale, which is vitally important in characterizing dominant modes of system behavior. Here, by combining topology with scale, we prove the existence of universal features which reveal the dominant scales of any network. We use these features to compare several canonical network types in the context of a social media discussion which evolves through the sharing of rumors, leaks and other news. Our analysis enables for the first time a universal understanding of the balance between loops and tree-like structure across network scales, and an assessment of how this balance interacts with the spreading of information online. Crucially, our results allow networks to be quantified and compared in a purely model-free way that is theoretically sound, fully automated, and inherently scalable.

This work is joint with Patrick Wolfe.

Sofia is a professor of Statistics, an honorary professor of Computer Science and a senior research associate of Mathematics at University College London. She joined UCL in 2007, before which she was a senior lecturer of statistics (associate professor) at Imperial College London (2006-2007), a lecturer of statistics (assistant professor) (2002-2006), where she also completed her PhD in 2003 and MSci in 2000. She has held three research fellowships while at UCL: UK Engineering and Physical Sciences Springboard fellowship as well as a five-year Leadership fellowship, and now holds a European Research Council Consolidator fellowship. Sofia has contributed to the study of stochastic processes; time series, random fields and networks. She is on the ICMS Programme Committee since September 2008, a member of the London Mathematical Society Research Meetings Committee,  a member of the London Mathematical Society Research Policy Committee and an associate Editor for Transactions in Mathematics and its Applications. Sofia is also a member of the Royal Society and British Academy Data Governance Working Group, and the Royal Society working group on machine learning.

PACM & CSML Joint Colloquium: Mean estimation: median-of-means tournaments

Speaker: 
Gábor Lugosi, ICREA & Pompeu Fabra University, Spain
Date: 
Oct 23 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

One of the most basic problems in statistics is how to estimate the expected value of a distribution, based on a sample of independent random draws. When the goal is to minimize the length of a confidence interval, the usual empirical mean has a sub-optimal performance, especially for heavy-tailed distributions. In this talk we discuss some estimators that achieve a sub-Gaussian performance under general conditions. The multivariate scenario turns out to be more challenging. We present an estimator with near-optimal performance. We also discuss how these ideas extend to regression function estimation.

The talk is based on joint work with Shahar Mendelson (Technion, Israel), Luc Devroye (Mcgill University, Canada), Matthieu Lerasle (CNRS, France) and Roberto Imbuzeiro Oliveira (IMPA, Brazil).

Gabor Lugosi is an ICREA Research Professor at the Pompeu Fabra University in Barcelona, Spain where he has been since 1996. He received his PhD in Electrical Engineering from the Hungarian Academy of Sciences in 1991. His research interests include the theory of machine learning,  combinatorial statistics, inequalities in probability, random graphs and random structures, and information theory.

PACM Colloquium: Symmetry methods for quantum variational principles and expectation value dynamics

Speaker: 
Cesare Tronci, University of Surrey, Guildford, UK
Date: 
Nov 6 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

Inspired by previous works by Kramer & Saraceno and Shi & Rabitz, this talk exploits symmetry methods for the variational formulation of different problems in physics and chemistry. First, I will use symmetry methods to provide new variational principles for the description of mixed quantum states, in various pictures including Schrödinger, Heisenberg, Dirac (interaction) and Wigner-Moyal. Then, after discussing Ehrenfest's mean-field model, I will modify its symmetry properties to provide a new variational principle for expectation value dynamics in general situations. Upon moving to the Hamiltonian approach, this construction provides a complete dynamical splitting between expectation values and quantum deviations. As we shall see, specializing to Gaussian states yields energy conserving variants of previous models from the chemistry literature. In the last part of the talk, I will discuss some of the geometric features emerging in coupled classical-quantum dynamics.

Cesare obtained a Laurea in Nuclear Engineering in May 2004 at the Politecnico di Torino (Italy). Then, after spending two years (06/2003 – 05/2005) at CERN (Switzerland) working on microwave electronics under the direction of Ugo Amaldi (also at TU München and TERA Foundation), he moved to the Theoretical Division (in the former Plasma Theory Group) of the Los Alamos National Lab (LANL, USA), where he visited Giovanni Lapenta (now at KU Leuven, Belgium) for several months. In 10/2005, Cesare entered a PhD program at Imperial College, under the direction of Darryl Holm. In his thesis, he worked on geometric analogies between kinetic theory and porous media equations to model the aggregation of ferromagnetic nanoparticles. Between 2006 and 2007, he also spent two summers at LANL, working with Bruce Carlsten in the former International, Space & Response Division (High Power Electrodynamics Group). In 09/2008, Cesare joined the Mathematics Section of EPF Lausanne (Switzerland) as a research assistant in Tudor Ratiu’s group (Geometric Analysis). Since 01/2012, he is Lecturer (Assistant Professor) in the Department of Mathematics of the University of Surrey and have visited several institutions in Europe and North America.

Joint CSML/PACM/EE Colloquium: Latent Variable Model, Matrix Estimation and Collaborative Filtering

Speaker: 
Devavrat Shah, Massachusets Institute of Technology
Date: 
Nov 13 2017 - 4:30pm
Event type: 
PACM Colloquium
Room: 
Bowen Hall Auditorium
Abstract: 

Estimating a matrix based on partial, noisy observations is prevalent in a variety of modern applications with recommendation system being a prototypical example. The non-parametric latent variable model provides canonical representation for such matrix data when the underlying distribution satisfies “exchangeability” with graphons and stochastic block model being recent examples of interest. Collaborative filtering has been a successfully utilized heuristic in practice since the dawn of e-commerce. In this talk, I will argue that collaborative filtering (and its variants) solve matrix estimation for a generic latent variable model with near optimal sample complexity.

The talk is based on joint works with

  1. Christina Lee (MSR), Yihua Li (MS) and Dogyoon Song (MIT)
  2. Christina Borgs (MSR), Jennifer Chayes (MSR) and Christina Lee (MIT)

Devavrat Shah is a Professor with the department of Electrical Engineering and Computer Science at Massachusetts Institute of Technology. His current research interests are at the interface of Statistical Inference and Stochastic Networks. His work has been recognized through career prizes including 2010 Erlang prize from the INFORMS Applied Probability Society and 2008 ACM Sigmetrics Rising Star Award. He is a distinguished young alumni of his alma mater IIT Bombay.

PACM Colloquium: The mathematics of charged liquid drops

Speaker: 
Cyrill Muratov, NJ Institute of Technology
Date: 
Nov 20 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

In this talk, I will present an overview of recent analytical developments in the studies of equilibrium configurations of liquid drops in the presence of repulsive Coulombic forces. Due to the fundamental nature of Coulombic interaction, these problems arise in systems of very different physical nature and on vastly different scales: from femtometer scale of a single atomic nucleus to micrometer scale of droplets in electrosprays to kilometer scale of neutron stars. Mathematically, these problems all share a common feature that the equilibrium shape of a charged drop is determined by an interplay of the cohesive action of surface tension and the repulsive effect of long-range forces that favor drop fragmentation. More generally, these problems present a prime example of problems of energy driven pattern formation via a competition of long-range attraction and long-range repulsion. In the talk, I will focus on two classical models - Gamow's liquid drop model of an atomic nucleus and Rayleigh's model of perfectly conducting liquid drops. Surprisingly, despite a very similar physical background these two models exhibit drastically different mathematical properties. I will discuss the basic questions of existence vs. non-existence, as well as some qualitative properties of global energy minimizers in these models, and present the current state of the art for this class of geometric problems of calculus of variations.

Cyrill Muratov is Professor of Mathematical Sciences at New Jersey Institute of Technology. He received his M.Sc. in Applied Mathematics and Physics from Moscow Institute of Physics and Technology, followed by a Ph. D. in Physics from Boston University and postdoctoral training in Applied Mathematics at the Courant Institute. His main research interests lie in understanding the emergence of complexity from basic constitutive laws in problems of science and engineering, using a combination of rigorous mathematical analysis, formal asymptotics and numerical simulations.

 

PACM Colloquium: Two problems involving breakup of a liquid film

Speaker: 
Jens Eggers, Bristol University
Date: 
Nov 27 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

Understanding the breakup of a liquid film is complicated by the fact that there is no obvious instability driving breakup: surface tension favors a film of uniform thickness over a deformed one. Here, we identify two mechanisms driving a film toward (infinite time) pinch-off. In the first problem, we show how the rise of a bubble is arrested in a narrow tube, on account of the lubricating film pinching off. In the second problem, breakup of a free liquid film is driven by a
strong temperature gradient across the pinch region. 

J. Eggers is a professor of Applied Mathematics at the University of Bristol. Dr. Eggers' career has been devoted to the understanding of self-similar phenomena. He has made fundamental contributions to our mathematical understanding of free-surface flows, in particular breakup and coalescence of drops. His work is instrumental in establishing the study singularities as a research field fluid dynamics and applied mathematics. With Marco Fontelos, he has recently published a book at Cambridge University Press, which presents a unifying view of singularities in Physics, Mathematics, and Engineering, and aims to make the subject accessible to a wider audience. He is a member of the Academy of Arts and Sciences in Erfurt, Germany, and a Fellow of the American Physical Society, and has been made a Euromech Fellow. Dr. Eggers' most recent work concerns the spatial structure of shock waves in compressible gas dynamics, and singularities in non-linear elasticity.

Phase Retrieval and systems of polynomial equations

Speaker: 
Dan Ediden, University of Missouri
Date: 
Dec 4 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

A signal vector can be easily reconstructed from a set of linear measurements such as the discrete Fourier transform. However, in many physical problems only the intensity, but not the phase, of the measurements can be obtained. From a mathematical perspective, the phase retrieval problem is to recover an unknown signal from the absolute values of a collection of measurements. This reconstruction problem has a long history in engineering and physics and arises in a variety of situations such as optics and speech recognition. In this talk we explain how, in many contexts, algebraic methods can be used to to estimate the minimum number of phaseless measurements needed to recover generic signals.

Dan Edidin is the Leonard Blumenthal Distinguished Professor of Mathematics at University of Missouri.  Originally trained in algebraic geometry, he received his PhD from MIT under the supervision of Joe Harris and Steve Kleiman and was a postdoc at University of Chicago with Bill Fulton. His research interests are on problems related to group actions on algebraic varieties in both pure and applied mathematics.

Spring 2018

PACM Colloquium

Speaker: 
Nikhil Srivastava, UC Berkeley
Date: 
Feb 5 2018 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

TBA

PACM Colloquium

Speaker: 
Tony Cai, Wharton School - UPenn
Date: 
Feb 26 2018 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

TBA