Eugene M. Luks Professor Emeritus   E-mail: luks AT uoregon DOT edu

Education

BS, 1960, City College of New York
PhD, 1966, Massachusetts Institute of Technology

Research Interests

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 problems involving algebraic structures such as groups.

Although there are numerous applications, the work was originally motivated by problems similar to testing graph isomorphism. This resulted in a new group-theoretic approach to the general problem and specifically in polynomial-time procedures for significant graph classes. Current projects tend to be aimed at improved algorithms for a wider class of group-theoretic problems, seeking efficient (especially polynomial-time) solutions to problems for which only asymptotically infeasible (e.g., exponential-time) approaches are currently known. There are also 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.

Publications

Group isomorphism with fixed subnormal chains, arXiv:1511.00151 [cs.CC] (2015).

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³log n) deterministic and an O(n³) 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³log n) deterministic and an O(n³) 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.  
Russian translation: Изоморфизм графов с ограниченными степенями вершин может быть установлен за полиномиальное время, 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-fonctorialité du H² en cohomologie non abélienne II, Comptes Rendus Acad. Sci. Paris, A, 282 (1976), 183-185, (with P. Dedecker).

Sur la non-fonctorialité du H² en cohomologie non abélienne 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 polynômes invariantes sur les algèbres 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.