Юджин М. Люкс

Юджин Михаил Лукс (род. около 1940 г.) — американский математик и ученый-компьютерщик , почетный профессор компьютерных и информатических наук в Университете Орегона . Он известен своими исследованиями проблемы изоморфизма графов и алгоритмов вычислительной теории групп .

Профессиональная карьера

Лукс учился на бакалавриате в Городском колледже Нью-Йорка , получив степень бакалавра в 1960 году. и продолжил обучение в аспирантуре Массачусетского технологического института , получив степень доктора математики в 1966 году под руководством Кенкичи Ивасавы . Он преподавал в Университете Тафтса с 1966 по 1968 год и в Университете Бакнелла с тех пор до 1983 года, когда он поступил на факультет Университета Орегона в качестве заведующего кафедрой компьютерных и информационных наук. Вышел на пенсию в 2006 году. но был отозван в 2012–2013 годах на должность временного председателя.

Награды и почести

В 1985 году Люкс получил премию Фулкерсона за свою работу, показавшую, что изоморфизм графов можно проверить за полиномиальное время для графов с ограниченной максимальной степенью . В 2012 году он стал членом Американского математического общества .

Избранные публикации

• Ферст, Меррик; Хопкрофт, Джон ; Люкс, Юджин М. (1980), «Алгоритмы с полиномиальным временем для групп перестановок» (PDF) , Труды 21-го симпозиума IEEE по основам информатики (FOCS'80) , стр. 36–41, doi : 10.1109/SFCS .1980.34 , HDL : 1813/6282 , S2CID   6943363 .
• Люкс, Юджин М. (1982), «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время», Journal of Computer and System Sciences , 25 (1): 42–65, doi : 10.1016/0022-0000(82) 90009-5 , S2CID   2572728 .
• Бабай, Ласло ; Люкс, Юджин М. (1983), «Каноническая маркировка графов», Труды 15-го симпозиума ACM по теории вычислений (STOC '83) , стр. 171–183, doi : 10.1145/800061.808746 , S2CID   12572142 .