Geometric group theory is the study of the relationship between the algebraic, geometric, and combinatorial properties of finitely generated groups. Here, we add to the dictionary of correspondences between geometric group theory and computational complexity. We then use these correspondences to establish limitations on certain models of computation.

In particular, we establish a connection between read-once oblivious branching programs and growth of groups. We then use Gromov's theorem on groups of polynomial growth to give a simple argument that if the word problem of a group \(G\) is computed by a non-uniform family of read-once, oblivious, polynomial-width branching programs, then it is computed by an \(O(n)\)-time uniform algorithm. That is, efficient non-uniform read-once, oblivious branching programs confer essentially no advantage over uniform algorithms for word problems of groups.

We also construct a group which faithfully encodes reversible circuits and note the correspondence between certain proof systems for proving equations of circuits and presentations of groups containing this group. We use this correspondence to establish a quadratic lower bound on the proof complexity of such systems, using geometric techniques which to our knowledge are new to complexity theory. The technical heart of this argument is a strengthening of the now classical theorem of geometric group theory that groups with linear Dehn function are hyperbolic. The proof also illuminates a relationship between the notion of quasi-isometry and models of computation that efficiently simulate each other.

This is a first stab at what a categorical theory of cryptography might look like. It essentially gives a generalized definition of a cryptosystem in categorical terms in terms of a category of interactive computations.

One interesting thing is that the definition given is a common generalization both of cryptosystems and error-correcting codes.

The document is pretty incomplete and doesn't cover some other ideas I had about how to formalize interactive proof systems and one-way functions in this setting.

A short expository article aimed at non-mathematicians explaining a bit about the result that IP = PSPACE, and how it would allow you to ensure that an AI is giving you good advice.

A tool for walking around the plane endowed with different Riemannian metrics. Includes the ability to write down custom metrics.

This was an introductory talk on expanders and some of their basic pseudorandomness/mixing properties.

Here is a little visualization of expanders I showed at the talk. Click to make it expand!

A talk on my senior thesis work applying string diagrams to program synthesis.