Building Babylon

Together with my colleagues Ryan Cao and Kunming Jiang, we re-derived the knowledge soundness of Groth16 as an entertaining exercise.

$$ \newcommand{\ff}[0]{\mathbb{F}} \newcommand{\ffOmega}[0]{\ff^\Omega} \newcommand{\ffOmegaSqrd}[0]{\ff^{\Omega^2}} \newcommand{\fxd}[0]{\ff[X]^{< d}} \newcommand{\fxdHalf}[0]{\ff[X]^{< {d/2}}} \newcommand{\RS}[0]{\mathrm{RS}} \newcommand{\RSd}[0]{\mathr…

(inspired by discussions with my colleagues Giorgos Zirdelis & Vishruti Ganesh; any mistakes are my own).

“How to Prove False Statements: Practical Attacks on Fiat-Shamir” (Khovratovich, Rothblum, Soukhanov; 2025) constructs families of circuits for which the GKR protocol, when made non-interactive by Fiat-Shamir heuristic, will prove false statements.

$\newcommand{\fxd}[0]{\mathbb{F}[X]^{< d}} \newcommand{\fxdone}[0]{\mathbb{F}[X]^{< d-1}} \newcommand{\RS}[0]{\mathrm{RS}} \newcommand{\drc}[0]{\mathrm{D}_{r, c}\,} \newcommand{\fo}[0]{\ff^\Omega} \newcommand{\eval}[0]{\mathrm{E}}$ Here we cover how to bu…

Reed-Solomon codes Let $\mathbb{F}$ be a finite field, and write $\mathbb{F}[X]^{< n}$ for the polynomials of degree less than $n$ over $\mathbb{F}$.

(The following thought experiment was suggested to me by my colleague Ryan Cao; mistakes and invective are my own).

A polynomial with coefficients in a field and of degree $< n$ is determined by its evaluations at any $n$ distinct points.

The Vandermonde matrix computes evaluations of polynomials from their coefficients via a matrix-vector product.

We recount here an elementary proof of associativity for the group law on a non-singular elliptic curve.

The following is intended as an introduction to finite fields for those with already some familiarity with algebraic constructions.

(This is an extremely useful fact with a straightforward proof.

While there is famously no “royal road to geometry”, I believe that there is a royal road to understanding the wonderful logUp, a lookup argument from Starkware’s Shahar Papini and Polygon’s Ulrich Haböck.

I recently enjoyed a talk by François Charton on “Transformers for maths, and maths for transformers” (recording).

Polynomials are formal sums.

This paper (arXiv), authored by Petersen, Borgelt, Kuehne and Deussen, was accepted for NeurIPs 2022.

Here is a nice simple example of bilinear pairing on an elliptic curve over a finite field.

The appearance of an elliptic curve from the point of view of the affine $(x,y)$ plane is familiar to us, but leaves us wondering what the curve might look like near the point at infinity (i.e. the identity element $\mathcal{O}$).

Here is a first example of an elliptic curve over a finite field where you can work everything out by hand.

Here are the slides from a talk I gave the Sydney machine learning meetup on Siegelmann and Sontag’s paper from 1995 “On the Computational Power of Neural Nets”, showing that recurrent neural networks are Turing complete.

I gave a talk last night at the Berlin machine learning meetup on learning graph embeddings in hyperbolic space, featuring the recent NIPS 2017 paper of Nickel & Kiela.

Nickel & Kiela had a great paper on embedding graphs in hyperbolic space at NIPS 2017.

I recently needed to demonstrate this fact to an audience that I could not assume would be familiar with Riemannian geometry, and it took some time to find a way to do it!

[These are the notes from a talk I gave at the seminar] Hierarchical softmax is an alternative to the softmax in which the probability of any one outcome depends on a number of model parameters that is only logarithmic in the total number of outcomes.

In their book “Perceptrons” (1969), Minsky and Papert demonstrate that a simplified version of Rosenblatt’s perceptron can not perform certain natural binary classification tasks, unless it uses an unmanageably large number of input predicates.

Suppose you have a model that depends on real-valued parameters, and that you would like to constrain these parameters to be non-negative.

Here we derive updates rules for the approximation of a row stochastic matrix by the product of two lower-rank row stochastic matrices using gradient descent.

I learnt of the 1944 experiment of Heider and Simmel in the Machine Intelligence workshop at NIPS 2016.

Non-negative matrix factorisation (NMF) learns to reconstruct samples as a superposition of their constituent parts.

Having trained a model, it is natural to want to understand how it works.

Adagrad is a learning regime that maintains separate learning rates for each individual model parameter.

We show that if the contour lines of a function are symmetric with respect to some rotation or reflection, then so is the evolution of gradient descent when minimising that function.

I prepared the following one-page overview of the short-time Fourier transform for a recent talk, perhaps it’ll be useful to others.

We aim to identify the assumptions that are implicit in the sampling of a continuous-time signal and in the subsequent application of the discrete Fourier transform (DFT).

Non-negative matrix factorisation (NMF) is a dimension reduction technique that is commonly applied in a number of different fields, for example: in topic modelling, applied to the document x word matrix; in speech processing, applied to the matrix of mag…

These are notes from a talk I presented at the seminar on June 22nd.

The paper Neural Word Embeddings as Implicit Matrix Factorization of Levy and Goldberg was published in the proceedings of NIPS 2014 (pdf).

The softmax function provides a convenient parameterisation of the probability distributions over a fixed number of outcomes.

Steffen Rendle and Christoph Freudenthaler (University of Konstanz), WSDM 2014.

We consider the “Weighted Approximate-Rank Pairwise-” (WARP-) loss, as introduced in the WSABIE paper of Weston et. al (2011, see references), in the context of making recommendations using implicit feedback data, where it has been shown several times to…

Below are the notes I made to prepare for a short talk given at our seminar on learning distance metrics, and the Mahalanobis distances in particular.

Recall that a symmetric matrix $M \in \mathbb{R}^{n \times n}$ is called positive semidefinite (“PSD”) if, for any $x \in \mathbb{R}^n$, we have $x^{T} M x \geqslant 0$.

In a paper with Adriaan Schakel, we presented controlled experiments for word embeddings using pseudo-words.

Below are the notes I prepared for a talk that I gave at our seminar on limiting distributions for (finite-state, time-homogeneous) Markov chains, drawing on PageRank as an example.

Pennington, Socher, Manning, 2014.

We show below that vectors drawn uniformly at random from the unit sphere are more likely to be orthogonal in higher dimensions.

This is the standard, elementary arithmetic proof that the marginal and conditional distributions of the multivariate Gaussian are again Gaussian with parameters expressible in terms of the covariance matrix of the original Gaussian.

(We needed this to derive the conditional distribution of a multivariate Gaussian).

Presented at NIPS 2014 (PDF) by Dai, Olah, Le and Corrado.

Below are notes from a talk on Expectation Maximisation I gave at our ML-learning group.