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.)
possible bridge between group growth theory and complexity theory?
cc.complexity theory;reference request;complexity classes;big picture;gr.group theory
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.