Eugene M. Luks

STOC Conference 1999 Conference Paper

Hypergraph Isomorphism and Structural Equivalence of Boolean Functions

• Eugene M. Luks

SODA Conference 1996 Conference Paper

Multiplicative Equations over Commuting Matrices

• László Babai
• Robert Beals
• Jin-Yi Cai
• Gábor Ivanyos
• Eugene M. Luks

FOCS Conference 1992 Conference Paper

Computing in Solvable Matrix Groups

• Eugene M. Luks

The author announces methods for efficient management of solvable matrix groups over finite fields. He shows that solvability and nilpotence can be tested in polynomial-time. Such efficiency seems unlikely for membership-testing, which subsumes the discrete-log problem. However, assuming that the primes in mod G mod (other than the field characteristic) are polynomially-bounded, membership-testing and many other computational problems are in polynomial time. These problems include finding stabilizers of vectors and of subspaces and finding centralizers and intersections of subgroups. An application to solvable permutation groups puts the problem of finding normalizers of subgroups into polynomial time. Some of the results carry over directly to finite matrix groups over algebraic number fields; thus, testing solvability is in polynomial time, as is testing membership and finding Sylow subgroups. >

STOC Conference 1991 Conference Paper

Fast Monte Carlo Algorithms for Permutation Groups

• László Babai
• Gene Cooperman
• Larry Finkelstein
• Eugene M. Luks
• Ákos Seress

STOC Conference 1990 Conference Paper

Computing in Quotient Groups

• William M. Kantor
• Eugene M. Luks

FOCS Conference 1988 Conference Paper

Fast Management of Permutation Groups

• László Babai
• Eugene M. Luks
• Ákos Seress

Novel algorithms for computation in permutation groups are presented. They provide an order-of-magnitude improvement in the worst-case analysis of the basic permutation-group problems, including membership testing and computing the order of the group. For deeper questions about the group, including finding composition factors, an improvement of up to four orders of magnitude is realized. These and other essential investigations are all accomplished in O(n/sup 4/log/sup c/n) time. The approach is distinguished by its recognition and use of the intrinsic structure of the group at hand. >

STOC Conference 1987 Conference Paper

Permutation Groups in NC

• László Babai
• Eugene M. Luks
• Ákos Seress

We show that the basic problems of permutation group manipulation admit efficient parallel solutions. Given a permutation group G by a list of generators, we find a set of NC-efficient strong generators in NC. Using this, we show, that the following problems are in NC: membership in G; determining the order of G; finding the center of G; finding a composition series of G along with permutation representations of each composition factor. Moreover, given G, we are able to find the pointwise stabilizer of a set in NC. One consequence is that isomorphism of graphs with bounded multiplicity of eigenvalues is in NC. The analysis of the algorithms depends, in several ways, on consequences of the classification of finite simple groups.

FOCS Conference 1986 Conference Paper

Parallel Algorithms for Permutation Groups and Graph Isomorphism

• Eugene M. Luks

We develop parallel techniques for dealing with permutation group problems. These are most effective on the class of groups with bounded non-abelian composition factors. For this class, we place in NC problems such as membership testing, finding the center and composition factors, and, of particular significance, finding pointwise-set-stabilisers. The last has applications to instances of graph-isomorphism and we show that NC contains isomorphism-testing for vertex-colored graphs with bounded color multiplicity, a problem not long known to be in polynomial time.

FOCS Conference 1985 Conference Paper

Fast Parallel Computation with Permutation Groups

• Eugene M. Luks
• Pierre McKenzie

We develop fast parallel solutions to a number of basic problems involving solvable and nilpotent permutation groups. Testing solvability is in NC, and RNC includes, for solvable groups, finding order, testing membership, finding the derived series and finding a composition series. Additionally, for nilpotent groups, one can, in RNC, find the center, a central composition series, and point-wise stabilizers of sets. There are applications to graph isomorphism. In fact, we exhibit a class of vertex-colored graphs for which determining isomorphism is NC-equivalent to computing ranks of matrices Over small fields. A useful tool is the observation that the problem of finding the smallest subspace containing a given set of vectors and closed under a given set of linear transformations (all over a small field) belongs to RNC.

STOC Conference 1983 Conference Paper

Canonical Labeling of Graphs

• László Babai
• Eugene M. Luks

We announce an algebraic approach to the problem of assigning canonical forms to graphs. We compute canonical forms and the associated canonical labelings (or renumberings) in polynomial time for graphs of bounded valence, in moderately exponential, exp(n ½ + ο(1) ),time for general graphs, in subexponential, n log n , time for tournaments and for 2-(ν,κ,λ) block designs with κ,λ bounded and n log log n time for λ-planes (symmetric designs) with λ bounded. We prove some related problems NP-hard and indicate some open problems.

FOCS Conference 1983 Conference Paper

Computational Complexity and the Classification of Finite Simple Groups

• László Babai
• William M. Kantor
• Eugene M. Luks

We address the graph isomorphism problem and related fundamental complexity problems of computational group theory. The main results are these: A1. A polynomial time algorithm to test simplicity and find composition factors of a given permutation group (COMP). A2. A polynomial time algorithm to find elements of given prime order p in a permutation group of order divisible by p. A3. A polynomial time reduction of the problem of finding Sylow subgroups of permutation groups (SYLFIND) to finding the intersection of two cosets of permutation groups (INT). As a consequence, one can find Sylow subgroups of solvable groups and of groups with bounded nonabelian composition factors in polynomial time. A4. A polynomial time algorithm to solve SYLFIND for finite simple groups. A5. An ncd/log d algorithm for isomorphism (ISO) of graphs of valency less than d and a consequent improved moderately exponential general graph isomorphism test in exp(c√n log n) steps. A6. A moderately exponential, n, c√n algorithm for INT. Combined with A3, we obtain an nc√n algorithm for SYLFIND as well. All these problems have strong links to each other. ISO easily reduces to INT. A subcase of SYLFIND was solved in polynomial time and applied to bounded valence ISO in [Lul]. Now, SYLFIND is reduced to INT. Interesting special cases of SYLFIND belong to NP ∩ coNP and are not known to have subexponential solutions. All the results stated depend on the classification of finite simple groups. We note that no previous ISO test had no(d) worst case behavior for graphs of valency less than d. It appears that unless there is another radical breakthrough in ISO, independent of the previous one, the simple groups classification is an indispensable tool for further developments.

FOCS Conference 1982 Conference Paper

An O(n^3 log n) Deterministic and an O(n^3) Probabilistic Isomorphism Test for Trivalent Graphs

• Zvi Galil
• Christoph M. Hoffmann
• Eugene M. Luks
• Claus-Peter Schnorr
• Andreas Weber 0006

The main results of this paper are an O(n3) probabilistic algorithm and an O(n3 log n) deterministic algorithm that test whether two given trivalent graphs are isomorphic. In fact, the algorithms construct the set of all isomorphisms of the two graphs. Variants of these algorithms construct the set of all automorphisms of a trivalent graph. The algorithms make use of some new improved permutation group algorithms that exploit the fact that the groups involved are 2-groups. A remarkable property of the probabilistic algorithm is that it computes Isoe, ei(X, Y), i = 1, .. ., m, m = O(n) (the set of all isomorhisms φ: X → Y with φ(e)=ei) for the cost of computing the single set Isoe, el(X, Y).

FOCS Conference 1980 Conference Paper

Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time

• Eugene M. Luks

Suppose we are given a set of generators for a group G of permutations of a colored set A. The color automorphism problem for G involves finding generators for the subgroup of G which stabilizes the color classes. Testing isomorphism of graphs of valence ≤ t is polynomial-time reducible to the color automorphism problem for groups with small simple sections. The algorithm for the latter problem involves several divide-and-conquer tricks. The problem is solved sequentially on the G-orbits. An orbit is broken into a minimal set of blocks permuted by G. The hypothesis on G guarantees the existence of a 'large' subgroup P which acts as a p-group on the blocks. A similar process is repeated for each coset of P on G. Some results on primitive permutation groups are used to show that the algorithm runs in polynomial time.

FOCS Conference 1980 Conference Paper

Polynomial-Time Algorithms for Permutation Groups

• Merrick L. Furst
• John E. Hopcroft
• Eugene M. Luks

A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is practical to use such a representation since many problems such as membership testing, equality testing, and inclusion testing are decidable in polynomial time. In addition, we demonstrate that the normal closure of a subgroup can be computed in polynomial time, and that this proceaure can be used to test a group for solvability. We also describe an approach to computing the intersection of two groups. The procedures and techniques have wide applicability and have recently been used to improve many graph isomorphism algorithms.