<p>There has been some recent work in terms of characterizing automorphism groups of strongly regular graphs using asymptotic group theory (e.g. <a href="http://people.cs.uchicago.edu/~laci/papers/14itcs.pdf">this paper</a>), which (for many reasons) is likely very closely related to the complexity of algorithms on strongly regular graphs that use group-theoretic methods, although exploiting such properties algorithmically is still an open question.</p>

CC BY-SA 3.0
2015-02-22T07:20:31.297Z
2015-02-22T07:20:31.297Z
Joe Bebel
<p>Maybe this is along the lines you are looking for: I wrote <a href="https://parametricity.com/posts/read-once-poly.html" rel="nofollow noreferrer">a blog post here</a> explaining how you can use Gromov's theorem on groups of polynomial growth to show that non-uniform read once automata are no more powerful than linear time Turing machines for deciding word problems of groups.</p>

<p>The basic idea is that groups with non-uniform read once automata necessarily have <a href="https://en.wikipedia.org/wiki/Growth_rate_(group_theory)#Polynomial_and_exponential_growth" rel="nofollow noreferrer">polynomial growth</a> (i.e., the number of elements with a word of length at most $r$ is $O(r^k)$ for some fixed $k$). By <a href="https://en.wikipedia.org/wiki/Gromov&#39;s_theorem_on_groups_of_polynomial_growth" rel="nofollow noreferrer">Gromov's theorem</a>, 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.</p>

CC BY-SA 3.0
2017-03-05T07:54:08.087Z
2017-03-14T05:41:07.573Z
2017-03-14T05:41:07.573Z
Izaak Meckler
<p><a href="https://rjlipton.wordpress.com/2013/06/20/three-theorems-about-growth/" rel="nofollow noreferrer">RJ Lipton conjectures</a> a link between group growth theory and complexity theory. Group growth theory has <a href="http://www.ams.org/journals/bull/0000-000-00/S0273-0979-2015-01475-8/S0273-0979-2015-01475-8.pdf" rel="nofollow noreferrer">undergone rapid advance</a> in the last decade and has many surface similarities/ parallels with complexity theory. (of course there are other deep <a href="https://cs.stackexchange.com/questions/14398/bridge-theorems-for-group-theory-and-formal-languages">known links</a> between TCS/ group theory.)</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>(eg conceivably there could be an intermediate link via boolean circuits etc.)</p>

CC BY-SA 3.0
2015-02-21T23:45:41.290Z
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
CC BY-SA 3.0
2015-02-22T04:30:19.843Z
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
CC BY-SA 3.0
2015-02-23T16:47:45.580Z
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 [chat] for anyone interested in following/ engaging with it more at length
vzn
<cc.complexity-theory><reference-request><complexity-classes><big-picture><gr.group-theory>
possible bridge between group growth theory and complexity theory?
vzn
# possible bridge between group growth theory and complexity theory?

(Asked by: username_0 on 2015-02-21)

[RJ Lipton conjectures](https://rjlipton.wordpress.com/2013/06/20/three-theorems-about-growth/) a link between group growth theory and complexity theory. Group growth theory has [undergone rapid advance](http://www.ams.org/journals/bull/0000-000-00/S0273-0979-2015-01475-8/S0273-0979-2015-01475-8.pdf) in the last decade and has many surface similarities/ parallels with complexity theory. (of course there are other deep [known links](https://cs.stackexchange.com/questions/14398/bridge-theorems-for-group-theory-and-formal-languages) 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.)

**Tags:** cc.complexity-theory, reference-request, complexity-classes, big-picture, gr.group-theory

> **Comments:**
> **username_1**: 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?  
> **username_1**: 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.  
> **username_0**: 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 [chat] for anyone interested in following/ engaging with it more at length  

---

## 2 answers

### Answer by username_2 on 2015-02-22. Score: 7 | Accepted answer

There has been some recent work in terms of characterizing automorphism groups of strongly regular graphs using asymptotic group theory (e.g. [this paper](http://people.cs.uchicago.edu/~laci/papers/14itcs.pdf)), which (for many reasons) is likely very closely related to the complexity of algorithms on strongly regular graphs that use group-theoretic methods, although exploiting such properties algorithmically is still an open question.


---

### Answer by username_3 on 2017-03-05. Score: 8

Maybe this is along the lines you are looking for: I wrote [a blog post here](https://parametricity.com/posts/read-once-poly.html) explaining how you can use Gromov's theorem on groups of polynomial growth to show that non-uniform read once automata are no more powerful than linear time Turing machines for deciding word problems of groups.

The basic idea is that groups with non-uniform read once automata necessarily have [polynomial growth](https://en.wikipedia.org/wiki/Growth_rate_(group_theory)#Polynomial_and_exponential_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](https://en.wikipedia.org/wiki/Gromov's_theorem_on_groups_of_polynomial_growth), 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.


---

