Izaak Meckler
How strong are geodesic circuits?

\(\newcommand{\ACC}{\mathrm{ACC}}\) \(\newcommand{\P}{\mathrm{P}}\) \(\newcommand{\poly}{\mathrm{poly}}\) \(\newcommand{\Poly}[1]{\mathrm{poly}(#1)}\) \(\newcommand{\NC}{\mathrm{NC}}\) \(\newcommand{\NP}{\mathrm{NP}}\)

People don't know how to prove things about \(\P/\poly\) so it is 'customary' to study poly-sized circuits with severe restrictions imposed. Two old favorites are \(\ACC^0\) and \(\NC^1\) which basically are two ways of putting bounds on the depth of a circuit.

A different way I've been thinking about weakening circuits is by putting geometric restrictions on them. By switching focus to reversible circuits (i.e., circuits made out of invertible gates), we see circuits as words in a certain (sequence of) presentations of the symmetric group (see my post for a few more details).

Also, one can put a certain coarse structure on this group which separates it into \(P\)-interreducible components, but I don't think many interesting things can be said here. (You make a set \(X\) controlled if for every sequence \((f_n, g_n) \in X\), \(f_n\) is \(\Poly{|f|}\) reducible to \(g_n\) and vice versa).

This is roughly the setting of geometric group theory, so I have been interested in investigating whether certain geometric constraints on circuits would make lower bounds easier to prove. One result so far is that a family of circuits lying on a geodesic cannot compute an \(\NP\)-hard function unless \(\P = \NP\). I think it should be possible to make this unconditional, as geodesic families of circuits ought to be quite weak.

One thing which seems interesting to me at the moment is the fact that the circuits one gets by taking a uniform \(\P\)-machine and unrolling it in the usual way are themselves quite uniform. Can something be said about the large scale geometric apparance of such a family?