Scalable Graph Algorithms

Monte Carlo
Advanced Monte Carlo Methods for Graphs
"Recent work in statistical physics has shown Monte Carlo methods may be accelerated using a variety of parallelization techniques, including parallel tempering, hybrid simulated annealing, population annealing, and Boltzmann resampling. We also find improvement in autocorrelation times by implementing cluster moves and reweighting techniques. We are currently investigating the efficiency of these methods applied to graphs, such as causal set spacetimes and random geometric graphs."
Parallel Tempering
Tensorial Parallel Tempering of Spin Systems
"Spin systems which exhibit critical phenomena and have rough free energy landscapes are often difficult to study due to ineffective sampling near the critical point and ground state. We study the effect of using multi-dimensional, or tensorial, parallel tempering of a system consisting of a mixture of Hamiltonians. Using techniques from information geometry, we calculate the optimal replica parameters which avoid critical surfaces and minimize the autocorrelation of samples near the ground state."
Bitset Algorithms for Graphical Data
"We consider compact graph representations using bitsets. Graph properties may be measured in a highly efficient manner by operating on these data structures with bitwise and bit-counting algorithms written directly in x64 assembly. We have shown such methods can improve runtimes by a factor of 1000 in applications where graphs are directed and acyclic."
Network Navigation
Greedy Routing in Random Geometric Graphs
"Geometric graphs in hyperbolic spaces explain the optimality of many network functions related to finding paths in the network without global knowledge of the network structure. Yet little is known about routing behavior in non-Riemannian latent spaces. We study the navigability of undirected random geometric graphs in three Lorentzian manifolds: the de Sitter spacetime, the Einstein-de Sitter spacetime, and an interpolating spacetime similar to our physical universe. We find graphs in such spacetimes are navigable only when dark energy is present."

Machine Learning and Artificial Intelligence

Protocols for Autodidactic Systems
"We consider a series of graph algorithms which constitute self-learning procedures. In physics, such systems may explain how the laws of physics themselves evolve in the early universe. Likewise, artificial intelligence seeks to explain how learning may arise naturally. Examples of protocols include precedence, extremal variety, renormalization-group neural networks, and abstract simplicial complexes decorated with Ising spins."
Bayesian Networks
Sequential Growth via Quantum Bayesian Networks
"We consider a quantum sequential growth algorithm for the early universe. Using the decoherent histories framework of quantum mechanics, and qubits which encode matter and causality degrees of freedom, we grow quantum graphs which converge to semi-classical causal sets. The transition probabilities in this system are inferred using a factorized Bayesian network. We are studying how attention networks and recurrent neural networks may be used extract the couplings required to simulate this on a quantum computer."
Supervised Learning
Deep Learning in Quantum Gravity
"Is machine learning a useful tool in quantum gravity? We claim it is, particularly for classification tasks. A simple proof-of-concept experiment showed a deep neural network can be trained to classify the dimension and manifold of causal sets sprinkled into various spacetimes. We are currently using graph neural networks to learn how causal sets grow into manifold-like structures."

Quantum Gravity and Cosmology

Lattice Gas
Dynamics of Causal Set Quantum Gravity
"We study 2D and 3D causal sets using a lattice gas model with toroidal spatial topology. Elements on a lattice undergo random ergodic moves in a Monte Carlo simulation whose measure is furnished by the Benincasa-Dowker action. After studying the phase structure in this fixed-topology system, we are considering topological changes to the lattice, so that the partition function includes a sum over topologies with fixed initial and final hypersurfaces."
Spinfoam Renormalization
Spin Foam Renormalization
"We study the coarse-graining procedure defined by the theory of tensor network renormalization applied to 3D spin foams in the fusion basis. Spin foam amplitudes are represented by high-dimensional tensors, and they are glued together using a very specific gluing algorithm. Every six iterations one cubic building block is transformed into a larger, coarser cubic building block. Not only are many iterations required to study the convergence of the singular values and extract the phase structure, but the high-dimensional tensors use an extreme amount of memory in excess of a terabyte."
Vacuum Selection
Multiverse String Theory
"F theory details a string landscape of at least 10755 geometries, each of which can support at least 10500 flux vacua. Somewhere within this landscape lies the Standard Model of Physics, yet there exist no good methods to fully explore such a vast space. We take a first step at characterizing the string landscape using a network model, where nodes are geometries and links represent simple topological transitions. This model is the first to give evidence that at late times in a bubble cosmology, there exists a heterogenous distribution of selected vacua."

Discrete Geometry

Bolza Surface
Ollivier-Ricci Curvature of Riemannian Spaces
"We study random geometric graphs embedded in the torus, sphere, and Bolza surface. Using these discrete geometric structures, we measure the Ollivier-Ricci curvature, which we have proven to be the only graph curvature measure that converges exactly to the curvature of the underlying manifold. Simulations use a variety of optimizations, including a multi-GPU graph construction algorithm and a multi-GPU implementation of the A* search algorithm."
Timelike Boundaries
Timelike Boundaries in Lorentzian Geometry
"What does a boundary look like in a discrete, non-local object like a causal set? Recent work showed causal sets can be partitioned in several ways which gives a characterization of the convex hull, and we developed an algorithm to measure the volume of timelike boundaries. Yet it remains unknown what the timelike boundary term for the causal set action will look like. To better understand boundaries, we are working to calculate the causal set equivalent of the Gibbons-Hawking-York terms from general relativity."