7
$\begingroup$

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.)

Improve this question
$\endgroup$
3
  • 7
    $\begingroup$ 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? $\endgroup$
    – Sasho Nikolov
    Commented Feb 21, 2015 at 23:45
  • 3
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Feb 22, 2015 at 4:30
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Feb 23, 2015 at 16:47

2 Answers 2

Reset to default
7
$\begingroup$

There has been some recent work in terms of characterizing automorphism groups of strongly regular graphs using asymptotic group theory (e.g. this paper), 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.

Improve this answer
$\endgroup$
8
$\begingroup$

Maybe this is along the lines you are looking for: I wrote a blog post here 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 (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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.