Eugene Luks

Eugene Michael Luks (* 7. Januar 1940 in New York City) ist ein US-amerikanischer Mathematiker und Informatiker. Er befasst sich mit dem Entwurf und der Analyse von Algorithmen in der Algebra.

Luks studierte am City College of New York mit dem Bachelor-Abschluss 1960 und wurde 1966 am Massachusetts Institute of Technology bei Kenkichi Iwasawa promoviert (Spherical Functions on GL(n) over P-Adic Fields).[1] Er lehrte von 1966 bis 1968 an der Tufts University und bis 1983 an der Bucknell University. Danach war er Professor an der University of Oregon. 2006 wurde er emeritiert (war aber noch einmal 2012/13 Lehrstuhlvertreter).

Anfangs befasste er sich mit Zahlentheorie und Liealgebren.

1985 erhielt er den Fulkerson-Preis für seine Arbeit zum Graphen-Isomorphismusproblem. Er zeigte, dass der Isormophismus von Graphen beschränkter Valenz in Polynomialzeit getestet werden kann.[2] Dafür entwarf er auch gruppentheoretische Algorithmen. Luks gab auch 1983 mit László Babai Schranken für das Wachstum der Komplexität mit der Anzahl der Knoten (die immer noch exponentiell wuchs für allgemeine Graphen).[3] Das war lange die beste Schranke, bis Laszlo Babai Ende 2015 ankündigte, eine bessere (quasipolynomiale) Schranke gefunden zu haben.

Außerdem befasst er sich mit Algorithmischer Gruppentheorie. Anwendungen sind zum Beispiel die Frage der Äquivalenz von Schaltkreisen und die Ausnutzung von Symmetrie im Constraint-Satisfaction-Problem.

2012 wurde er Fellow der American Mathematical Society.

Schriften

[Bearbeiten | Quelltext bearbeiten]
  • Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences, Band 25, 1982, S. 42–65
  • mit László Babai: Canonical labeling of graphs, Proceedings of the 15th ACM Symposium on Theory of Computing (STOC '83), 1983, S. 171–183
  • mit Merrick Furst, John Hopcroft: Polynomial-time algorithms for permutation groups, Proceedings of the 21st IEEE Symposium on Foundations of Computer Science (FOCS'80), 1980, S. 36–41
  • Computing the composition factors of a permutation group in polynomial time, Combinatorica, Band 7, 1987, S. 87–99.
  • Permutation groups and polynomial-time computation. In: Groups and Computation, DIMACS Ser. in Discr. Math. and Theor. Computer Sci., Band 11, 1993, S. 139–175
  • Hypergraph Isomorphism and Structural Equivalence of Boolean Functions, in: 31st ACM STOC, 1999, S. 652–658
  • mit 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, S. 162–171
[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. ↑ Eugene Michael Luks im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendetVorlage:MathGenealogyProject/Wartung/name verwendet
  2. ↑ Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences, Band 25, 1982, S. 42–65
  3. ↑ Babai, Luks, Canonical labeling of graphs, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), 1983, S. 171–183
Personendaten
NAME Luks, Eugene
ALTERNATIVNAMEN Luks, Eugene Michael
KURZBESCHREIBUNG US-amerikanischer Mathematiker
GEBURTSDATUM 7. Januar 1940
GEBURTSORT New York City, New York, Vereinigte Staaten