## Eugene M. Luks## Professor Emeritus
Phone: 541-346-1379 E-mail: luks AT cs uoregon edu |

BS, 1960, City College of New York

PhD, 1966, Massachusetts Institute of Technology

Recent research by Professor Luks has involved the design and analysis of algorithms, with a focus on computational solutions to algebraic problems. The main objective is an understanding of the computational complexity and practical solvability of questions that can make use of algebraic structures such as groups.

Although there are many applications, a particular driving force behind the research has been the connections to problems similar to graph isomorphism. There is strong evidence that these group-theoretic problems are not NP-complete. Nevertheless, although graph isomorphism is rarely difficult in practice, it is not known to be in polynomial time. Introducing new algebraic procedures, Professor Luks's work has led to polynomial-time procedures for significant graph classes and to the best timing for general graphs.

A principal goal of current projects is improved sequential algorithms for group-theoretic problems, seeking to extend the class of algebraic problems that have efficient solutions. This involves broad investigations aimed at finding feasible (polynomial-time) solutions to problems for which only asymptotically infeasible (exponential-time) have been available. Deeper studies of certain fundamental questions is intended to improve algorithmic performance; for example, for problems involving permutation groups, timing has been improved by an order of magnitude in most basic problems and as much as four orders of magnitude for deeper structural questions; other improvements have resulted from the introduction of random methods. Furthermore, implementations have been obtained that are practically efficient while retaining their guarantee of asymptotic efficiency.

A second major effort is directed toward the parallelization of the machinery for algebraic computation. In the case of group-theoretic software, almost all the traditional programs appear to rely on inherently sequential (nonparallelizable) procedures. Thus, the parallel approach necessarily rests on entirely new foundations for computation in algebraic structures. In particular, the verification of correctness has made use of very recent breakthroughs in finite group theory. A remarkable spin-off of these new techniques has been their evident reapplication to (practically as well as asymptotically) efficient sequential computation.

There are frequent instances of applications to other domains. Examples include use of symmetry in constraint-satisfaction problems and application of group-theoretic tools to testing equivalence of switching circuits.

For his innovations in graph isomorphism and related issues, Professor Luks was awarded the Delbert Ray Fulkerson Prize in Discrete Mathematics by the Mathematical Programming Society and the American Mathematical Society. In 2012, Professor Luks was elected to the inaugural class of Fellows of the American Mathematical Society.

*Polynomial-time normalizers,*
Discrete Mathematics and Theoretical Computer Science,
13:4 (2011) 61-96,
(with T. Miyazaki).

*Testing isomorphism of modules,*
Journal of Algebra 320 (2008), 4020-4029,
(with P. Brooksbank).

*Combinatorics of singly-repairable families,*
The Electronic Journal of Combinatorics,
12 (2005), #R59,
(with A. Roy).

* Generalizing boolean satisfiability III: Implementaion,*
Journal of Artificial Intelligence Research,
23, (2005), 441-531,
(with H. Dixon, D. Hofer, M. Ginsberg, A. Parkes).

* Generalizing boolean satisfiability II: Theory,*
Journal of Artificial Intelligence Research,
22, (2004), 481-534,
(with H. Dixon, M. Ginsberg, A. Parkes).

* Implementing a generalized version of resolution,*
19th National Conference on Artificial Intelligence (2004), 55-60,
(with H. Dixon, M. Ginsberg, D. Hofer, A. Parkes).

*The complexity of symmetry-breaking formulas,*
Annals of Mathematics and Artificial
Intelligence, 41 (2004), 19-45,
(with A. Roy).

*Polynomial-time normalizers for permutation groups
with restricted composition factors*,
Proceedings of
the 2002 International Symposium on Symbolic and Algebraic Computation,
176-183, (with T. Miyazaki).

*Symmetry breaking in constraint satisfaction,*
Seventh International Symposium
on Artificial Intelligence and Mathematics, 200, (with A. Roy).

*Generalized derivations of Lie algebras,*
Journal of Algebra, 228 (2000), 165-203, (with G. Leger).

*Hypergraph isomorphism and structural equivalence of boolean functions,*
Proceedings 31st ACM Symposium on Theory of Computing, 1999, 652-658.

*Sylow subgroups in parallel,*
Journal of Algorithms, 31 (1999),
132-195, (with W. M Kantor and P. D. Mark).

*Some algorithms for nilpotent permutation groups,*
Journal of
Symbolic Computation, 23, 1997, 335-354, (with F. Rákóczi
and C. R. B. Wright).

*Short presentations for finite groups*,
Journal of Algebra, 194
(1997), 79-112, (with L. Babai, A. J. Goodman, W. M. Kantor, and P. P. Pálfy).

*Fast management of permutation groups I,*
SIAM Journal of Computing,
26 (1997), 1310-1342, (with L. Babai and Á. Seress).

*Computing the Fitting subgroup and solvable radical of small-base
permutation groups in nearly linear time,* in Groups and Computation,
DIMACS series in Discrete Mathematics and Theoretical Computer Science
28 (1997), 169-181, (with Á. Seress).

*Multiplicative equations over commuting matrices*, Proceedings
7th ACM-SIAM Symposium on Discrete Algorithms, 1996, 498-507, (with L. Babai,
R. Beals, J-Y. Cai, and G. Ivanyos).

*Symmetry-breaking predicates for search problems*, Proceedings
5th International Conference on Principles of Knowledge Representation
and Reasoning, 1996, 148-159, (with J. Crawford, M. Ginsberg, and A. Roy).

*Fast Monte Carlo algorithms for permutation groups,*
Journal of
Computer and Systems Science, 50 (1995) 296-308, (with L. Babai, G. Cooperman,
L. Finkelstein, and Á. Seress).

*Computing normalizers in permutation p-groups*, Proceedings of
the 1994 International Symposium on Symbolic and Algebraic Computation,
139-146, (with F. Rákóczi and C. R. B. Wright).

*P-complete permutation group problems*, Proceedings of the 25th
Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus
Numerantium 100 (1994), 119-124, (with K. Blaha).

*Permutation groups and polynomial-time computation,*in Groups
and Computation, DIMACS series in Discrete Mathematics and Theoretical
Computer Science 11 (1993), 139-175.

*Computing composition series of primitive groups,* in Groups and
Computation, DIMACS series in Discrete Mathematics and Theoretical Computer
Science 11 (1993), 1-15, (with L. Babai, Á Seress).

*Computing in solvable matrix groups,*
Proceedings 33rd IEEE Symposium
on the Foundations of Computer Science, 1992, 111-120.

*Fast Monte Carlo Algorithms for Permutation Groups,*
Proceedings 23rd ACM Symposium
on Theory of Computing, 1991, 90-100,
(with L. Babai,
G. Cooperman, L. Finkelstein and Á Seress).

*Gargoyles for computer science,*
The Mathematical Intelligencer,
13, Fall 1991, 24.

*Computing in quotient groups,*
Proceedings 22nd ACM Symposium
on Theory of Computing, 1990, 524-534, (with W. M. Kantor).

*Lectures on polynomial-time computation in groups,*
Technical Report NU-CCS-90-16, Northeastern University, 1990.

*Reduction of group constructions to point stabilizers,* Proc.
ACM International Symp. on Symbolic and Algebraic Computation, 1989, 351-356,
(with G. Cooperman, L. Finkelstein).

*Fast management of permutation groups,* Proc. 29th IEEE Symp.
on the Foundations of Comp. Sci., 1988, 272-282, (with L. Babai, Á
Seress).

*Parallel computation in solvable permutation groups,* Journal of
Computer and System Sciences (Special Issue), 37 (1988), 39-62, (with P.
McKenzie).

*Permutation groups in NC,*
Proc. 19th ACM Symp. on Theory of Computing,
1987, 409-420, (with L. Babai, Á Seress).

*Computing the composition factors of a permutation group in polynomial
time,* Combinatorica 7 (1987), 87-99.

*An O(n ^{3}log n) deterministic and an O(n^{3})
Las Vegas isomorphism
test for trivalent graphs,* Journal of the ACM, 34, (1987) 513-531, (with
Z. Galil, C.M. Hoffmann, C.P. Schnorr, A. Weber).

*Parallel algorithms for permutation groups and graph isomorphism,*
Proc. 27th IEEE Symp. on the Foundations of Comp. Sci., 1986, 292-302.

*Fast parallel computation with permutation groups,* Proc. 26th
IEEE Symp. on the Foundations of Comp. Sci., 1985, 505-514, (with P. McKenzie).

*Strategy, non-transitive dominance and the exponential distribution,*
Australian Journal of Statistics, 26, 1984, 111-118, (with K. Kaminsky,
P. Nelson).

*Computational complexity and the classification of finite simple
groups,* Proc. 24th IEEE Symp. on the Foundations of Comp. Sci. 1983,
162-171, (with L. Babai, W.M. Kantor).

*Canonical labeling of graphs,* Proc. 15th ACM Symp. on Theory
of Computing, 1983, 171-183, (with L. Babai).

*An O(n ^{3}log n) deterministic and an O(n^{3})
probabilistic isomorphism test for trivalent graphs,* Proceedings 23rd IEEE Symp. on Foundations
of Comp. Sci. (1982), 118-125, (with Z. Galil, C.M. Hoffmann, C.P. Schnorr,
A. Weber).

*
Isomorphism of graphs of bounded valence can be tested in polynomial
time,,*
Journal of Computer and System Sciences, 25, 1982, 42-65. Translated
into Russian in "Cybernetics Sbornik", ed. O.B. Lupanov, Moscow (1985),
72-101.

*Polynomial time algorithms for permutation groups, *
Proc. 21st IEEE
Symp. on Foundations of Comp. Sci. (1980), 36-41, (with M. Furst, J. Hopcroft).

*Isomorphism of graphs of bounded valence can be tested in polynomial
time,* Proc. 21st IEEE Symp. on Foundations of Comp. Sci. (1980), 42-49.

*A subexponential algorithm for trivalent graph isomorphism,* Proc.
11th Southeastern Conf. Combinatorics, Graph Theory, and Computing, 1980,
in Congressum Numerantium 3, (with M. Furst, J. Hopcroft).

*Derivation towers of Lie algebras,* Journal of Algebra 61, (1979),
280-288.

*What is the typical nilpotent Lie algebra?*
in "Computers in the
Study of Nonassociative Rings and Algebras", ed. R. Beck, B. Kolman, Academic
Press (1977), 189-208.

*Sur la non-fonctorialite du H^2 en cohomologie non abelienne II,*
Comptes Rendus Acad. Sci. Paris, A, 282 (1976), 183-185, (with P. Dedecker).

*Sur la non-fonctorialite du H^2 en cohomologie non abelienne I,*
Comptes
Rendus Acad. Sci. Paris, A, 282 (1976), 139-141, (with P. Dedecker).

*A characteristically nilpotent Lie algebra can be a derived algebra,*
Proceedings of the Amer. Math. Soc. 56, (1976), 42-44.

*An urn model and the prediction of order statistics,* Communications
in Statistics 4 (1975), 245-250, (with K. Kaminsky, P. Nelson).

*Correction and comment concerning "On derivations and holomorphs
of nilpotent Lie algebras",*
Nagoya Math. Journal 59, (1975), 217-218, (with G. Leger).

*Sur les fonctions polynomes invariantes sur les algebres de Lie,*
Comptes Rendus Acad. Sci. Paris, A, 280, (1975), 1177-1179, (with G. Leger).

*Normalizers of linear Lie algebras,* Linear and Multilinear Algebra
2, (1974), 151-160.

*Cohomology of nilradicals of Borel subalgebras,* Transactions of the
Amer. Math. Soc. 195, (1974), 305-316, (with G. Leger).

*Cohomology and weight systems for nilpotent Lie algebras,* Bulletin
of the Amer. Math. Soc. 80, (1974), 77-80, (with G. Leger).

*Cohomology theorems for Borel-like solvable Lie algebras in arbitrary
characteristic,* Canadian Journal of Math. 24 (1972), 1019-1026, (with G.
Leger).

*On a duality for metabelian Lie algebras,* Journal of Algebra 21 (1972),
266-270, (with G. Leger).

*On nilpotent groups of algebra automorphisms,* Nagoya Math. Journal
46, (1972), 87-95, (with G. Leger).

*On derivations and holomorphs of nilpotent Lie algebras,*
Nagoya Math.
Journal 44, (1971), 39-50, (with G. Leger).

*Lie algebras with only inner derivations need not be complete,*
Journal
of Algebra 15, (1970), 280-282.

*On the mean duration of a ball and cell game;
a first passage problem,*
Annals of Math. Statistics 27, (1966), 517-521, (with H. Dym).

*Spherical functions on GL _{n} over p-adic fields,* doctoral dissertation,
MIT, 1966.