Asymptotic invariants, complexity of groups and related problems

DOI10.1007/s13373-011-0008-1zbMath1293.20041arXiv1012.1325MaRDI QIDQ3143713

Mark V. Sapir

Publication date: 3 December 2012

Published in: Bulletin of Mathematical Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.1325

zbMATH Keywords

computational complexity; asymptotic cones; word problem; hyperbolic groups; isoperimetric functions; conjugacy problem; Dehn functions; Higman embeddings

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

20F50: Periodic groups; locally finite groups

20F65: Geometric group theory

20F38: Other groups related to topology or analysis

20F69: Asymptotic properties of groups

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

20F67: Hyperbolic groups and nonpositively curved groups

20-02: Research exposition (monographs, survey articles) pertaining to group theory

Related Items

Taming the hydra: The word problem and extreme integer compression, On groups with locally compact asymptotic cones, The rapid decay property and centroids in groups, Logspace computations in graph products, The isoperimetric spectrum of finitely presented groups, Algorithmically complex residually finite groups, A Higman embedding preserving asphericity, Balanced finite presentations of the trivial group

Cites Work

• The isomorphism problem for all hyperbolic groups.
• Quadratic equations over free groups and free products
• A finitary version of Gromov's polynomial growth theorem.
• Almost all one-relator groups with at least three generators are residually finite.
• Metabelian groups with quadratic Dehn function and Baumslag-Solitar groups.
• Finite-model theory -- A personal perspective
• A combination theorem for negatively curved groups
• Amenable semigroups
• Zur Theorie der meßbaren Gruppen
• Groups, the theory of ends, and context-free languages
• Gromov's theorem on groups of polynomial growth and elementary logic
• The Dehn function of Richard Thompson's group \(F\) is quadratic.
• Free and fragmenting filling length.
• Groups with small Dehn functions and bipartite chord diagrams.
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Group-based cryptography
• On group-theoretic models of randomness and genericity.
• A course in formal languages, automata and groups
• The solvability problem for quadratic equations over free groups is NP-complete
• Snowflake groups, Perron-Frobenius eigenvalues and isoperimetric spectra.
• Lacunary hyperbolic groups. With an appendix by Michael Kapovich and Bruce Kleiner.
• The Dehn function of Stallings' group.
• Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski
• The isomorphism problem for toral relatively hyperbolic groups.
• Filling Riemannian manifolds
• Unsolvability of the universal theory of finite groups
• The accessibility of finitely presented groups
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Trees, valuations, and the Bieri-Neumann-Strebel invariant
• Carnot-Carathéodory metrics and quasiisometries of symmetric spaces of rank 1
• Smoothness of the convex hull of planar Brownian motion
• Cyclic splittings of finitely presented groups and the canonical JSJ deccomposition
• Some general algorithms. I: Arithmetic groups
• Some general algorithms. II: Nilpotent groups
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• Cogrowth and amenability of discrete groups
• Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings
• Quadratic isometric functions of the Heisenberg groups. A combinatorial proof
• Mapping tori of free group automorphisms are coherent
• A finiteness property and an automatic structure for Coxeter groups
• Isoperimetric inequalities and the homology of groups
• Isoperimetric inequalities for the fundamental groups of torus bundles over the circle
• Recognizing the 3-sphere
• Introductory notes on Richard Thompson's groups
• The class of groups all of whose subgroups with lesser number of generators are free is generic
• On the asymptotic cone of groups satisfying a quadratic isoperimetric inequality
• An isoperimetric inequality for the Heisenberg groups
• Higher connectedness of asymptotic cones.
• Random walk in random groups.
• Non-amenable finitely presented torsion-by-cyclic groups.
• Isoperimetric inequalities for nilpotent groups.
• The Tits alternative for \(\text{Out}(F_n)\). I: Dynamics of exponentially-growing automorphisms
• Rectifiable sets in metric and Banach spaces
• There is only one gap in the isoperimetric spectrum
• Polynomial maps over finite fields and residual finiteness of mapping tori of group endomorphisms
• Asymptotic cones of finitely presented groups
• Homomorphism diagrams of surface groups
• The isomorphism problem for hyperbolic groups. I
• Isoperimetric and isodiametric functions of groups
• Isoperimetric functions of groups and computational complexity of the word problem
• On polyhedral retracts and compactifications of locally symmetric spaces
• Filling in solvable groups and in lattices in semisimple groups.
• Canonical representatives and equations in hyperbolic groups
• A short proof that a subquadratic isoperimetric inequality implies a linear one
• Statistical properties of finitely presented groups
• Distinguished subgroups and quotients of hyperbolic groups
• Isoperimetric functions of finitely generated nilpotent groups
• Conjugacy and dynamics in Thompson's groups.
• Outer automorphisms of free Burnside groups.
• Gromov hyperbolic spaces and the sharp isoperimetric constant
• A topological Tits alternative.
• Tree-graded spaces and asymptotic cones of groups. (With an appendix by Denis Osin and Mark Sapir).
• Growth of finitely generated solvable groups
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• An introduction to right-angled Artin groups.
• Existential questions in (relatively) hyperbolic groups.
• Space functions of groups
• Separable and tree-like asymptotic cones of groups
• APPROXIMATING THE FIRST L²-BETTI NUMBER OF RESIDUALLY FINITE GROUPS
• Search and witness problems in group theory
• Residual properties of 1-relator groups
• Stable group theory and approximate subgroups
• SOLVING THE WORD PROBLEM IN REAL TIME
• EXPLICIT CONSTRUCTIONS OF UNIVERSAL ℝ-TREES AND ASYMPTOTIC GEOMETRY OF HYPERBOLIC SPACES
• Conway's Tiling Groups
• Subgroups of finitely presented groups
• THE DOUBLE EXPONENTIAL THEOREM FOR ISODIAMETRIC AND ISOPERIMETRIC FUNCTIONS
• ISODIAMETRIC AND ISOPERIMETRIC INEQUALITIES FOR GROUP PRESENTATIONS
• SUBGROUPS OF FINITELY PRESENTED GROUPS WITH SOLVABLE CONJUGACY PROBLEM
• Polynomial Maps over p -Adics and Residual Properties of Mapping Tori of Group Endomorphisms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• Currents in metric spaces
• Groups acting on trees: From local to global structure
• Lattices in product of trees
• Isoperimetric inequalities for soluble groups
• Mapping class groups are automatic
• Makanin's algorithm for word equations-two improvements and a generalization
• The quadratic isoperimetric inequality for mapping tori of free group automorphisms
• THE CONJUGACY PROBLEM IS SOLVABLE IN FREE-BY-CYCLIC GROUPS
• Topologies on pseudo-trees and applications
• RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS
• Foliations for solving equations in groups: free, virtually free, and hyperbolic groups
• ON SYSTEMS OF EQUATIONS IN A FREE GROUP
• Relational queries computable in polynomial time
• PERIODIC FACTOR GROUPS OF HYPERBOLIC GROUPS
• ALMOST EVERY GROUP IS HYPERBOLIC
• A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
• Universal Spaces for R-Trees
• The Conjugacy Problem and Subgroups of Finite Index
• On the Complexity of Familiar Functions and Numbers
• Generic properties of finitely presented groups and howson's theorem
• On Dehn functions of free products of groups
• Fractional isoperimetric inequalities and subgroup distortion
• ON RESIDUALING HOMOMORPHISMS AND G-SUBGROUPS OF HYPERBOLIC GROUPS
• THE FREE BURNSIDE GROUPS OF SUFFICIENTLY LARGE EXPONENTS
• Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
• The SQ-universality of hyperbolic groups
• ON THE COMBINATION THEOREM FOR NEGATIVELY CURVED GROUPS
• Diagram groups
• Hyperbolic groups and free constructions
• Polynomial upper bounds for the Dehn function of R. Thompson's group F
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• Asymptotic Cones of Finitely Generated Groups
• A property of subgroups of infinite index in a free group
• The geometry of higman‐neumann‐neumann extensions
• Turing machines and the spectra of first-order formulas
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• QUASI-ISOMETRY INVARIANTS AND ASYMPTOTIC CONES
• The conjugacy problem and Higman embeddings
• FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY
• Semihyperbolic Groups
• ALGORITHMIC PROBLEMS IN VARIETIES
• Hyperbolic groups and their quotients of bounded exponents
• THE GALLERY LENGTH FILLING FUNCTION AND A GEOMETRIC INEQUALITY FOR FILLING LENGTH
• A FINITELY PRESENTED GROUP WITH TWO NON-HOMEOMORPHIC ASYMPTOTIC CONES
• Nilpotent groups without exactly polynomial Dehn function
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• Courbure mésoscopique et théorie de la toute petite simplification
• An Embedding Theorem for Finitely Generated Groups
• Heegaard Splittings and Splitting Homomorphisms
• A non-cyclic one-relator group all of whose finite quotients are cyclic
• The Degree of Polynomial Growth of Finitely Generated Nilpotent Groups
• A Finitely Presented Group Whose 3-Dimensional Integral Homology is not Finitely Generated
• The decision problem for some classes of sentences without quantifiers