Publications and preprints

Linear Transformer Topological Masking with Graph Random Features
Preprint, under review
Isaac Reid, Kumar Avinava Dubey, Deepali Jain, Will Whitney, Amr Ahmed, Joshua Ainslie, Alex Bewley, Mithun Jacob, Aranyak Mehta, David Rendleman, Connor Schenck, Richard E. Turner, René Wagner, Adrian Weller, Krzysztof Choromanski
How can you efficiently incorporate information about the underlying graph structure into a linear attention transformer, where the attention matrix is never explicitly instantiated in memory? Using GRFs, of course
Paper

Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs
Preprint, under review
Krzysztof Choromanski*, Isaac Reid*, Arijit Sehanobish, Avinava Dubey
By simulating correlated random walks on an ensemble of graphs, you can estimate the graph kernel between any given pair in linear time
Paper

Variance-Reducing Couplings for Random Features: Perspectives from Optimal Transport
Preprint, under review
Isaac Reid, Stratis Markou, Krzysztof Choromanski, Richard E. Turner, Adrian Weller
Variance reduction in Monte Carlo is really a multi-marginal optimal transport problem, and treating it as such gives us tools to sample more efficiently in Euclidean and discrete space.
Paper

Universal General Graph Random Features
ICLR 2024
Isaac Reid*, Krzysztof Choromanski*, Eli Berger*, Adrian Weller
You give me an arbitrary function of a weighted adjacency matrix, I give you a random feature mechanism to approximate it efficiently (name changed during review)
Paper

Repelling Random Walks
ICLR 2024
Isaac Reid, Eli Berger, Krzysztof Choromanski, Adrian Weller
The QMC scheme below wasn’t so good after all; now we correlate walker directions in an algorithm of broader interest
Paper

Quasi-Monte Carlo Graph Random Features
NeurIPS 2023, accepted as spotlight paper
Isaac Reid, Krzysztof Choromanski, Adrian Weller
A QMC scheme that induces correlations between the lengths random walks on a graph, with possible applications in bioinformatics and graph-based Transformers
Paper Code

Simplex Random Features
ICML 2023, accepted with oral presentation
Isaac Reid, Krzysztof Choromanski, Valerii Likhosherstov, Adrian Weller
Derivation of a provably optimal random feature mechanism for unbiased approximation of the Gaussian kernel, motivated by a host of new analytical results and tested with extensive Transformer experiments
Paper Code

Entanglement Barriers in Dual-Unitary Circuits
Phys. Rev. B 104, 014301 – Published 1 July 2021
Isaac Reid, Bruno Bertini
Exact characterisation of the dynamics of quantum entanglement arising after a quantum quench in a many-body, locally interacting system, including both the integrable and completely chaotic regimes.
Paper