Eugene M. Luks

Professor Emeritus

 

 

Phone: 541-346-1379

E-mail: luks AT cs uoregon 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 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.

Publications

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(n3log n) deterministic and an O(n3) 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(n3log n) deterministic and an O(n3) 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 GLn over p-adic fields, doctoral dissertation, MIT, 1966.