Article

On the diameter of finite groups

Authors:

A. SeressAuthors Info & Claims

SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science

Pages 857 - 865 vol.2

https://doi.org/10.1109/FSCS.1990.89608

Published: 22 October 1990 Publication History

Publisher Site

Abstract

The diameter of a group G with respect to a set S of generators is the maximum over g in G of the length of the shortest word in S union S/sup -1/ representing g. This concept arises in the contexts of efficient communication networks and Rubik's-cube-type puzzles. 'Best' generators are pertinent to networks, whereas 'worst' and 'average' generators seem more adequate models for puzzles. A substantial body of recent work on these subjects by the authors is surveyed. Regarding the 'best' case, it is shown that, although the structure of the group is essentially irrelevant if mod S mod is allowed to exceed (log mod G mod )/sup 1+c/(c>0), it plays a strong role when mod S mod =O(1).

Cited By

View all

Petit CQuisquater J(2015)Cryptographic Hash Functions and Expander GraphsLNCS Essays on The New Codebreakers - Volume 910010.1007/978-3-662-49301-4_19(304-311)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-662-49301-4_19
Rozenman EShalev AWigderson ABabai L(2004)A new family of Cayley expanders (?)Proceedings of the thirty-sixth annual ACM symposium on Theory of computing10.1145/1007352.1007423(445-454)Online publication date: 13-Jun-2004
https://dl.acm.org/doi/10.1145/1007352.1007423
Babai LFriedl KStricker M(1993)Decomposition of *-closed algebras in polynomial timeProceedings of the 1993 international symposium on Symbolic and algebraic computation10.1145/164081.164098(86-94)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1145/164081.164098

Recommendations

Wide Diameter of Cayley Digraphs of Finite Cyclic Groups
ISPAN '08: Proceedings of the The International Symposium on Parallel Architectures, Algorithms, and Networks

According to recent studies, communication networks built on extremal Cayley digraphs of finite cyclic groups have many advantages over that based on n-cubes. Extremal Cayley digraphs have been studied extensively in recent years. In this paper, we ...
Computing generators of groups preserving a bilinear form over residue class rings

We construct generators for symplectic and orthogonal groups over residue class rings modulo an odd prime power. These generators have been implemented and are available in the computer algebra system GAP.
Finite groups admitting an oriented regular representation

In this paper, we investigate finite groups admitting an oriented regular representation and we give a partial answer to a 1980 question of Lazslo Babai: Which [finite] groups admit an oriented graph as a DRR? It is easy to see and well-understood that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science

October 1990

ISBN:081862082X

Publisher

IEEE Computer Society

United States

Publication History

Published: 22 October 1990

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Petit CQuisquater J(2015)Cryptographic Hash Functions and Expander GraphsLNCS Essays on The New Codebreakers - Volume 910010.1007/978-3-662-49301-4_19(304-311)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-662-49301-4_19
Rozenman EShalev AWigderson ABabai L(2004)A new family of Cayley expanders (?)Proceedings of the thirty-sixth annual ACM symposium on Theory of computing10.1145/1007352.1007423(445-454)Online publication date: 13-Jun-2004
https://dl.acm.org/doi/10.1145/1007352.1007423
Babai LFriedl KStricker M(1993)Decomposition of *-closed algebras in polynomial timeProceedings of the 1993 international symposium on Symbolic and algebraic computation10.1145/164081.164098(86-94)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1145/164081.164098

Abstract

Cited By

Recommendations

Wide Diameter of Cayley Digraphs of Finite Cyclic Groups

Computing generators of groups preserving a bilinear form over residue class rings

Finite groups admitting an oriented regular representation

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations