There is increasing anecdotal evidence of a move of software development projects and employment from North America and Western Europe to Asia and Eastern Europe. This panel will address the current and potential impact of such software offshoring on academic programs in software engineering.

Permutation representations constructed from matrix groups defined over finite fields often have very high degree. New techniques are presented for performing effective computations with the resulting permutation group. These techniques are designed to work in an environment in which the degree of the permutation group is considered too large to permit the use of standard permutation algorithms for solving problems such as computing the order of the group and testing simplicity. The theory has been successfully tested on a representation of the sporadic simple group Ly, discovered by Lyons [10]. In [5], a permutation representation was constructed for Ly of degree 9,606,125 on a conjugacy class of subgroups of order 3. Using this permutation representation and no specific knowledge of the group, we are able to apply our methods to construct a base of at most four points for the resulting permutation group, compute its order and verify simplicity. Monte Carlo algorithms for group membership presented in [2] are used to improve the performance of these algorithms.

New techniques, both theoretical and practical, are presented for constructing a permutation representation for a matrix group. We assume that the resulting permutation degree, n, can be 10,000,000 and larger. The key idea is to build the new permutation representation using the conjugation action on a conjugacy class of subgroups of prime order. A unique signature for each group element corresponding to the conjugacy class is used in order to avoid matrix multiplication. The requirement of at least n matrix multiplications would otherwise have made the computation hopelessly impractical. Additional software optimizations are described, which reduce the CPU time by at least an additional factor of 10. Further, a special data structure is designed that serves both as a search tree and as a hash array, while requiring space of only 1.6n log2 n bits.

Article A fast cyclic base change for permutation groups Share on Authors: Gene Cooperman View Profile , Larry Finkelstein View Profile Authors Info & Claims ISSAC '92: Papers from the international symposium on Symbolic and algebraic computationAugust 1992 Pages 224–232https://doi.org/10.1145/143242.143316Online:01 August 1992Publication History 0citation234DownloadsMetricsTotal Citations0Total Downloads234Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Nearly linear time algorithms for permutation groups with a small base Authors: László Babai Dept. of Comp. Science, University of Chicago, Chicago, Illinois and Dept. of Algebra, Eötvös University, Budapest, Hungary H-1088 Dept. of Comp. Science, University of Chicago, Chicago, Illinois and Dept. of Algebra, Eötvös University, Budapest, Hungary H-1088View Profile , Gene Cooperman College of Comp. Science, Northeastern University, Boston, Mass. College of Comp. Science, Northeastern University, Boston, Mass.View Profile , Larry Finkelstein College of Comp. Science, Northeastern University, Boston, Mass. College of Comp. Science, Northeastern University, Boston, Mass.View Profile , Ákos Seress Dept. of Mathematics, Ohio State University, Columbus, Ohio Dept. of Mathematics, Ohio State University, Columbus, OhioView Profile Authors Info & Claims ISSAC '91: Proceedings of the 1991 international symposium on Symbolic and algebraic computationJune 1991 Pages 200–209https://doi.org/10.1145/120694.120724Online:01 June 1991Publication History 19citation320DownloadsMetricsTotal Citations19Total Downloads320Last 12 Months9Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Fast Monte Carlo algorithms for permutation groups Authors: László Babai Univ. of Chicago, Chicago, IL Univ. of Chicago, Chicago, ILView Profile , Gene Cooperman Northeastern Univ., Boston, MA Northeastern Univ., Boston, MAView Profile , Larry Finkelstein Northeastern Univ., Boston, MA Northeastern Univ., Boston, MAView Profile , Eugene Luks Univ. of Oregon, Eugene Univ. of Oregon, EugeneView Profile , Ákos Seress Ohio State Univ., Columbus Ohio State Univ., ColumbusView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 90–100https://doi.org/10.1145/103418.103435Published:03 January 1991Publication History 14citation519DownloadsMetricsTotal Citations14Total Downloads519Last 12 Months55Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A new random base change algorithm is presented for a permutation group G acting on n points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm. To achieve this time bound, the algorithm requires a random generator Rand(G) producing a random element of G with the uniform distribution and so that each call to Rand(G) takes time O(log(|G|)n). The random base change algorithm has probability 1 -- 1/|G|2 of completing in time O(log2(|G|)n) and outputting a data structure for representing the point stabilizer sequence relative to the new ordering which requires O(log(|G|)n) space and which can be used to test group membership in time O,(log(|G|)n). The time to build a data structure for computing a Rand(G) with the above properties from a strong generating set for G is dominated by the time to construct the strong generating set from the original set of generators.

The construction of point stabilizer subgroups is a problem which has been studied intensively. [1, 4, 5, 10, 11, 12, 14] This work describes a general reduction of certain group constructions to the point stabilizer problem. Examples are given for the centralizer, the normal closure, and a restricted group intersection problem. For the normal closure problem, this work provides an alternative to current algorithms, which are limited by the need for repeated closures under conjugation. For the centralizer and restricted group intersection problems, one can use an existing point stabilizer sequence along with a recent base change algorithm [2] to avoid generating a new point stabilizer sequence. This reduces the time complexity by at least an order of magnitude. Algorithms and theoretical time estimates for the special case of a small base are also summarized. An implementation is in progress.

The computation of a strong generating set for a permutation group acting on a set $\Omega $ of n points is the fundamental operation that underlies most of the algorithms in computational group theory. Sims gave a change of basis algorithm that transforms a strong generating set relative to one ordering of $\Omega $ into a strong generating set relative to a different ordering. Base change is crucial for many of the important algorithms that have been implemented in the Cayley system, and is also important for many applications of computational group theory to combinatorial and search problems. Sims’s base change has worst-case time $O(n^5 )$. The main result of this paper is a new change of basis algorithm that has worst-case time $O(n^3 )$.