Eugene Luks

from Wikipedia, the free encyclopedia

Eugene Michael Luks (born January 7, 1940 in New York City ) is an American mathematician and computer scientist. He deals with the design and analysis of algorithms in algebra.

Luks graduated from City College of New York with a bachelor's degree in 1960 and received his PhD in 1966 from the Massachusetts Institute of Technology with Kenkichi Iwasawa (Spherical Functions on GL (n) over P-Adic Fields) . He taught at Tufts University from 1966 to 1968 and at Bucknell University until 1983 . He was then a professor at the University of Oregon . In 2006 he retired (but was again deputy chair in 2012/13).

At first he dealt with number theory and Lie algebras.

In 1985 he received the Fulkerson Prize for his work on the graph isomorphism problem . He showed that the isormophism of graphs of bounded valence can be tested in polynomial time. For this he also designed group theoretical algorithms. In 1983 Luks and László Babai gave bounds for the growth of complexity with the number of nodes (which still grew exponentially for general graphs). This was the best bound for a long time, until Laszlo Babai announced at the end of 2015 that they had found a better (quasi-polynomial) bound.

He also deals with algorithmic group theory. Applications are, for example, the question of the equivalence of circuits and the utilization of symmetry in the constraint-satisfaction problem .

In 2012 he became a Fellow of the American Mathematical Society .

Fonts

  • Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences, Volume 25, 1982, pp. 42-65
  • with László Babai: Canonical labeling of graphs, Proceedings of the 15th ACM Symposium on Theory of Computing (STOC '83), 1983, pp. 171-183
  • with Merrick Furst, John Hopcroft : Polynomial-time algorithms for permutation groups, Proceedings of the 21st IEEE Symposium on Foundations of Computer Science (FOCS'80), 1980, pp. 36-41
  • Computing the composition factors of a permutation group in polynomial time, Combinatorica, Volume 7, 1987, pp. 87-99.
  • Permutation groups and polynomial-time computation. In: Groups and Computation, DIMACS Ser. in Discr. Math. And Theor. Computer Sci., Vol. 11, 1993, pp. 139-175
  • Hypergraph Isomorphism and Structural Equivalence of Boolean Functions, in: 31st ACM STOC, 1999, pp. 652-658
  • with Laszlo Babai, William Kantor : Computational complexity and the classification of finite simple groups, Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), 1983, pp. 162-171

Web links

Individual evidence

  1. ↑ Eugene Luks in the Mathematics Genealogy Project (English)Template: MathGenealogyProject / Maintenance / id used
  2. ^ Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences, Volume 25, 1982, pp. 42-65
  3. ↑ Babai, Luks, Canonical labeling of graphs, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), 1983, pp. 171-183
personal data
SURNAME Luks, Eugene
ALTERNATIVE NAMES Luks, Eugene Michael
BRIEF DESCRIPTION American mathematician
DATE OF BIRTH January 7, 1940
PLACE OF BIRTH New York City , New York , United States