Decision problems – those in which the goal is to return an answer of “YES" or “NO" – are at the heart of the theory of computational complexity, and remain the most studied problems in the theoretical algorithms community. However, in many real-world applications it is not enough just to decide whether the problem under consideration admits a solution: we often want to find all solutions, or at least count (either exactly or approximately) their  total number. It is clear that finding or counting all solutions is at least as computationally difficult as deciding whether there exists a single solution, and  indeed in many cases it is strictly harder (assuming P is not equal NP) even to count approximately the number of solutions than it is to decide whether there exists at least one.

In this talk I will discuss a restricted family of problems, in which we are interested in solutions of a given size: for example, solutions could be copies of a specific k-vertex graph H in a large host graph G, or more generally k-vertex subgraphs of G that have some specified property (e.g. k-vertex subgraphs that are connected). In this setting, although exact counting is strictly harder than decision (assuming standard assumptions in parameterised complexity), the methods typically used to separate approximate counting from decision break down. Indeed, I will demonstrate a method that, subject to certain additional assumptions, allows us to transform an efficient decision algorithm for a problem of this form into an approximate counting algorithm with essentially the same running time.

This is joint work with John Lapinskas (Bristol) and Holger Dell (ITU Copenhagen).

Measurement outcomes in quantum theory are randomly distributed, and local measurements of the energy density of a QFT exhibit nontrivial fluctuations even in a vacuum state. This talk will present recent progress in determining the probability distribution for such measurements. In the specific case of 1+1 dimensional CFT, there are two methods (one based on Ward identities, the other on "conformal welding") which can lead to explicit closed-form results in some cases. The analogous problem for the free field in 1+3 dimensions will also be discussed.

 I will review some of the major research themes in Quantum Chaos over the past 50 years, and some of the questions currently attracting attention in the mathematics and physics literatures.

The aim of this talk is to give an overview about the structure theory of finite dimensional RCD metric measure spaces. I will first focus on rectifiability, existence, uniqueness and constancy of the dimension of tangents up to negligible sets.
Then I will motivate why boundaries of sets of finite perimeter are natural codimension one objects to look at in this framework and present some recent structure results obtained in their study.
This is based on joint works with Luigi Ambrosio, Elia Bruè and Enrico Pasqualetto.
 

Knotoids are a generalisation of knots that deals with open curves. In the past few years, they’ve been extensively used to classify entanglement in proteins. Through a double branched cover construction, we prove a 1-1 correspondence between knotoids and strongly invertible knots. We characterise forbidden moves between knotoids in terms of equivariant band attachments between strongly invertible knots, and in terms of crossing changes between theta-curves. Finally, we present some applications to the study of the topology of proteins. This is based on joint works with D.Buck, H.A.Harrington, M.Lackenby and with D. Goundaroulis.

Federer’s characterization, which is a central result in the theory of functions of bounded variation, states that a set is of finite perimeter if and only if n−1-dimensional Hausdorff measure of the set's measure-theoretic boundary is finite. The measure-theoretic boundary consists of those points where both the set and its complement have positive upper density. I show that the characterization remains true if the measure-theoretic boundary is replaced by a smaller boundary consisting of those points where the lower densities of both the set and its complement are at least a given positive constant.

Numerous researchers recently applied empirical spectral analysis to the study of modern deep learning classifiers. We identify and discuss an important formal class/cross-class structure and show how it lies at the origin of the many visually striking features observed in deepnet spectra, some of which were reported in recent articles and others unveiled here for the first time. These include spectral outliers and small but distinct bumps often seen beyond the edge of a "main bulk". The structure we identify organizes the coordinates of deepnet features and back-propagated errors, indexing them as an NxC or NxCxC array. Such arrays can be indexed by a two-tuple (i,c) or a three-tuple (i,c,c'), where i runs across the indices of the train set; c runs across the class indices and c' runs across the cross-class indices. This indexing naturally induces C class means, each obtained by averaging over the indices i and c' for a fixed class c. The same indexing also naturally defines C^2 cross-class means, each obtained by averaging over the index i for a fixed class c and a cross-class c'. We develop a formal process of spectral attribution, which is used to show the outliers are attributable to the C class means; the small bump next to the "main bulk" is attributable to between-cross-class covariance; and the "main bulk" is attributable to within-cross-class covariance. Formal theoretical results validate our attribution methodology.
We show how the effects of the class/cross-class structure permeate not only the spectra of deepnet features and backpropagated errors, but also the gradients, Fisher Information matrix and Hessian, whether these are considered in the context of an individual layer or the concatenation of them all. The Kronecker or Khatri-Rao product of the class means in the features and the class/cross-class means in the backpropagated errors approximates the class/cross-class means in the gradients. These means of gradients then create C and C^2 outliers in the spectrum of the Fisher Information matrix, which is the second moment of these gradients. The outliers in the Fisher Information matrix spectrum then create outliers in the Hessian spectrum. We explain the significance of this insight by proposing a correction to KFAC, a well known second-order optimization algorithm for training deepnets.

We study nearly singular PDEs that arise in the solution of linear elasticity and incompressible flow. We will demonstrate, that due to the nearly singular nature, standard methods for the solution of the linear systems arising in a finite element discretisation for these problems fail. We motivate two key ingredients required for a robust multigrid scheme for these equations and construct robust relaxation and prolongation operators for a particular choice of discretisation.