These are some questions I've been thinking about lately. The bounty for answering any of them is your choice of $5, a nice cup of coffee, or a portrait drawn by me.
Ideas may be misguided and/or obviously wrong. Please get in touch if that's the case! Or if you're interested in talking about any of them with me.
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.
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!