The era of multi-messenger astronomy is well and truly upon us, with 90 compact binaries observed since the Advanced LIGO detectors saw first light in 2015. Despite our very own cosmic backyard, the Milky Way, being ripe with prospective sources for ground-based gravitational wave detectors, the closest source detected thus far (GW170817, the famed binary neutron star merger) was at a distance of 40 Mpc. In this talk, I will outline a number of prospective Galactic multi-messenger sources, and discuss several ways in which their detection over the next twenty years can be improved through both experimental and analytical techniques.
Geometrically, a linear program is a polyhedron together with an orientation of its graph. A simplex method determines a path from any given starting vertex to the sink. The centerpiece of any simplex algorithm is the pivot rule that successively selects outgoing edges along the path. We introduce normalized-weight pivot rules, a class of pivot rules that are memory-less, that subsume many of the most-used pivot rules, and that can be parametrized in a natural continuous manner. We introduce two polytopes that capture the behavior of normalized-pivot rules on polytopes and linear programs. On the one hand, this gives a new perspective on the performance of pivot rules. On the other hand, our constructions generalize classical constructions (e.g. monotone path polytopes) and objects (e.g. permutahedra, associahedra, multiplihedra) from geometric combinatorics, This is joint work with Alex Black, Jesus De Loera, and Niklas Lütjeharms.
Conformal field theories (CFTs) are ubiquitous in theoretical physics as fixed points of renormalization, descriptions of critical systems and more. In these theories the conformal symmetry is a powerful tool in the computation of correlation functions, especially in 2 dimensions where the conformal algebra is infinite. Discretization of field theories is another powerful tool, where the theory on the lattice is both mathematically well-defined and easy to put on a computer. In this talk I will outline how these are combined using a discrete version of the 2d conformal algebra that acts in lattice models. I will also discuss recent work on convergence of this discretization, as well as on applications to non-unitary CFTs that appear in descriptions of problems of interest in condensed matter physics such as polymers, percolation and disordered systems.
I plan to survey some parts of Strassen's seminal body of work on the theory of asymptotic spectra, in which optimization and symmetry play crucial roles. In particular, I will motivate and explain the notion of asymptotic spectra, Strassen's duality theorem (far reaching generalization of linear programming duality, with connections to Positivstellensatz), and Strassen's connectivity theorem of the spectra of matrix multiplication.
The Kronecker coefficients of the symmetric group are the multiplicities of irreducible representations in the decomposition of the tensor product of two other irreducible representations. Ever since their definition by Murnaghan more than 80 years ago they've presented a major mystery and open problem in Algebraic Combinatorics. Recently they have come to play a crucial role in Geometric Complexity Theory in the quest for separation of VP and VNP. In this talk I'll give a broad overview of this topic with respect to combinatorics, asymptotics and computational complexity.
Logarithmic Sobolev inequalities (LSI) were first introduced by Gross in the 1970s as an equivalent formulation of hypercontractivity. LSI have been well studied in the past few decades and found applications to information theory, optimal transport, and graph theory. Recently matrix-valued LSI have been an active area of research. Matrix-valued LSI of Lindblad operators are closely related to decoherence of open quantum systems. In this talk, I will present recent results on matrix-valued LSI, in particular a geometric approach to matrix-valued LSI of Lindblad operators. This talk is based on joint work with Li Gao, Marius Junge, and Nicholas LaRacuente.
Understanding IP ownership and ensuring that commercialization of research provides broad societal and economic benefit both in Canada and abroad is extremely important. Perimeter Institute is also acutely aware that entrepreneurial oriented faculty and graduate students want to engage in commercial enterprise (i.e., through contract research and licensing opportunities with industry or independently with their own research outcomes). In this colloquium you will learn the basics about the different types of IP protection available and some of the most common pitfalls to avoid. Hear how IP is used to commercialize technology through licensing or start-up creation.
The state of a system of several quantum particles is an element in the tensor product of Hilbert spaces. In certain situations, the inner product requirement can be relaxed. Quantum states then turn into tensors, and tools and intuition from quantum information, algebraic geometry and algebraic complexity can connect. I will explain the two main traits of application, each leading to an optimization problem. The first is to quantum entanglement - the strong correlations among quantum particles - leading to an optimization over moment polytopes. The second is to many-body physics, where tensor networks are used as an ansatz class to describe the intricate correlations in quantum materials.
We study the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most d in n variables with only poly(n,d) L operations with high probability. This exceeds the expectations implicit in Smale's 17th problem. This is joint work with Felipe Cucker and Pierre Lairez, see arXiv:2010.10997.
Sampling from classical probability distributions is an important task with applications in a wide range of fields, including computational science, statistical physics, and machine learning. In this seminar, I will present a general strategy of solving sampling problems on a quantum computer. The entire probability distribution is encoded in a quantum state such that a measurement of the state yields an unbiased sample. I will discuss the complexity of preparing such states in the context of several toy models, where a polynomial quantum speedup is achieved. The speedup can be understood in terms of the properties of classical and quantum phase transitions, which establishes a connection between computational complexity and phases of matter. To conclude, I will comment on the prospects of applying this approach to challenging, real-world tasks.
The simplest homogeneous polynomials with nonnegative coefficients are products of linear forms Prod_{A}(X) associated with nonnegative matrices A. We prove that for any H-Stable(homogeneous and stable) polynomial p with P(E) = 1, where E is the vector of all ones, it's value p(X) = Prod_{A(X)}(X), where A(X) is nonnegative matrix with unit row sums and the vector of column sums equal to the gradient of p at E. I will first explain some intuition, and history, behind the result; sketch the proof and present a few applications and generalizations of this "productization" property. (Joint work with Jonathan Leake).