# possible bridge between group growth theory and complexity theory?

RJ Lipton conjectures a link between group growth theory and complexity theory. Group growth theory has undergone rapid advance in the last decade and has many surface similarities/ parallels with complexity theory. (of course there are other deep known links between TCS/ group theory.)

has anyone seen a link between group growth theory and complexity theory? eg have any complexity class separations been found expressible in this framework, etc?

(eg conceivably there could be an intermediate link via boolean circuits etc.)

• Some more intuition why one should expect a connection would be nice. I am not really finding the conjecture you are claiming in the blog post either. Can you be more specific about which part of the post you are referring to? – Sasho Nikolov Feb 21 '15 at 23:45
• Actually results on growth in groups help in proving that certain Cayley graphs expand, and Cayley graphs provide a large class of the known explicit constructions of expander families. Explicit expander families of course have many applications in computer science and complexity theory. – Sasho Nikolov Feb 22 '15 at 4:30
• like RJL see some basic similarities/ connections but didnt want to bias/ limit answers with preconceptions. drawing out the parallels is something closer to a research program & would take more than just a few sentences. another possible intermedate bridge between the two (besides circuits) is cellular automata. can sketch out/ expand at length more in Theoretical Computer Science Chat for anyone interested in following/ engaging with it more at length – vzn Feb 23 '15 at 16:47

The basic idea is that groups with non-uniform read once automata necessarily have polynomial growth (i.e., the number of elements with a word of length at most $r$ is $O(r^k)$ for some fixed $k$). By Gromov's theorem, this implies that the group is virtually nilpotent. There is work giving linear time algorithms for the word problems of such groups, so that's that.