Geometric complexity theory is an approach towards solving computational complexity lower bounds questions using algebraic geometry and representation theory. This talk contains an introduction to geometric complexity theory and a presentation of some recent results. Along the way connections to the study of secant varieties and to classical combinatorial and representation theoretic conjectures will be pointed out.

A topology optimization problem for Stokes flow finds the optimal material distribution of a fluid in Stokes flow that minimizes the fluid’s power dissipation under a volume constraint. In 2003, T. Borrvall and J. Petersson [1] formulated a nonconvex optimization problem for this objective. They proved the existence of minimizers in the infinite-dimensional setting and showed that a suitably chosen finite element method will converge in a weak(-*) sense to an unspecified solution. In this talk, we will extend and refine their numerical analysis. In particular, we will show that there exist finite element functions, satisfying the necessary first-order conditions of optimality, that converge strongly to each isolated local minimizer of the problem.

/

Fully nonlinear PDEs involving the eigenvalues of matrix-valued differential operators (such as the Hessian) have been the subject of intensive study over the last few decades, since the seminal work of Caffarelli, Kohn, Nirenberg and Spruck. In this talk I will discuss some recent joint work with Luc Nguyen on the regularity theory for a large class of these equations, with a particular emphasis on a special case known as the sigma_k-Yamabe equation, which arises in conformal geometry. 

[1] T. Borrvall, J. Petersson, Topology optimization of fluids in Stokes flow, International Journal for Numerical Methods in Fluids 41 (1) (2003) 77–107. doi:10.1002/fld.426.

Coronary heart disease is characterised by the formation of plaque on artery walls, restricting blood flow. If a plaque deposit ruptures, blood clot formation (thrombosis) rapidly occurs with the potential to fatally occlude the vessel within minutes. Von Willebrand Factor (vWF) is a shear-sensitive protein which has a critical role in blood clot formation in arteries. At the high shear rates typical in arterial constrictions (stenoses), vWF undergoes a conformation change, unfolding and exposing binding sites and facilitating rapid platelet deposition. 

To understand the effect of  stenosis geometry and blood flow conditions on the unfolding of vWF and subsequent platelet binding, we developed a continuum model for the initiation of thrombus formation by vWF in an idealised arterial stenosis. In this talk I will discuss modelling proteins in flow using viscoelastic fluid models, the insight asymptotic reductions can offer into this complex system and some of the challenges of studying fast arterial blood flows. 

The well known node2vec algorithm has been used to explore network structures and represent the nodes of a graph in a vector space in a way that reflects the structure of the graph. Random walks in node2vec have been used to study the local structure through pairwise interactions. Our motivation for this project comes from a desire to understand higher-order relationships by a similar approach. To this end, we propose an extension of node2vec to a method for representing the k-simplices of a simplicial complex into Euclidean space. 

In this talk I outline a way to do this by performing random walks on simplicial complexes, which have a greater variety of adjacency relations to take into account than in the case of graphs. The walks on simplices are then used to obtain a representation of the simplices. We will show cases in which this method can uncover the roles of higher order simplices in a network and help understand structures in graphs that cannot be seen by using just the random walks on the nodes. 

Reducing a chain complex (whilst preserving its homotopy-type) using algebraic Morse theory ([1, 2, 3]) gives the same end-result as Gaussian elimination, but AMT does it only on certain rows/columns and with several pivots (in all matrices simultaneously). Crucially, instead of doing costly row/column operations on a sparse matrix, it computes traversals of a bipartite digraph. This significantly reduces the running time and memory load (smaller fill-in and coefficient growth of the matrices). However, computing with AMT requires the construction of a valid set of pivots (called a Morse matching).

In [4], we discover a family of Morse matchings on any chain complex of free modules of finite rank. We show that every acyclic matching is a subset of some member of our family, so all maximal Morse matchings are of this type.

Both the input and output of AMT are chain complexes, so the procedure can be used iteratively. When working over a field or a local PID, this process ends in a chain complex with zero matrices, which produces homology. However, even over more general rings, the process often reveals homology, or at least reduces the complex so much that other algorithms can finish the job. Moreover, it also returns homotopy equivalences to the reduced complexes, which reveal the generators of homology and the induced maps $H_{*}(\varphi)$. 

We design a new algorithm for reducing a chain complex and implement it in MATHEMATICA. We test that it outperforms other CASs. As a special case, given a sparse matrix over any field, the algorithm offers a new way of computing the rank and a sparse basis of the kernel (or null space), cokernel (or quotient space, or complementary subspace), image, preimage, sum and intersection subspace. It outperforms built-in algorithms in other CASs.

References

[1]  M. Jöllenbeck, Algebraic Discrete Morse Theory and Applications to Commutative Algebra, Thesis, (2005).

[2]  D.N. Kozlov, Discrete Morse theory for free chain complexes, C. R. Math. 340 (2005), no. 12, 867–872.

[3]  E. Sköldberg, Morse theory from an algebraic viewpoint, Trans. Amer. Math. Soc. 358 (2006), no. 1, 115–129.

[4]  L. Lampret, Chain complex reduction via fast digraph traversal, arXiv:1903.00783.

Contagion models on networks can be used to describe the spread of information, rumours, opinions, and (more topically) diseases through a population. In the simplest contagion models, each node represents an individual that can be in one of a number of states (e.g. Susceptible, Infected, or Recovered), and the states of the nodes evolve according to specified rules. Even with simple Markovian models of transmission and recovery, it can be difficult to compute the dynamics of contagion on large networks: running simulations can be slow, and the system of master equations is typically too large to be tractable.

 One approach to approximating contagion dynamics is to assume that each node state is independent of the neighbouring node states; this leads to a system of ODEs for the node state probabilities (the “first-order approximation”) that always overestimates the speed of infection spread. This approach can be made more sophisticated by introducing pair approximations or higher-order moment closures, but this dramatically increases the size of the system and slows computations. In this talk, I will present some alternative node-based approximations for contagion dynamics. The first of these is exact on trees but will always underestimate the speed of infection spread on a network with loops. I will show how this can be combined with the classic first-order node-based approximation to obtain a node-based approximation that has similar accuracy to the pair approximation, but which is considerably faster to solve.

Crystal Structure Prediction aims to reveal the properties that stable crystalline arrangements of a molecule have without stepping foot in a laboratory, consequently speeding up the discovery of new functional materials. Since it involves producing large datasets that themselves have little structure, an appropriate classification of crystals could add structure to these datasets and further streamline the process. We focus on geometric invariants, in particular introducing the density fingerprint of a crystal. After exploring its computations via Brillouin zones, we go on to show how it is invariant under isometries, stable under perturbations and complete at least for an open and dense space of crystal structures.