Дьёрдь Элекеш

Дьёрдь Элекеш (19 мая 1949 г. – 29 сентября 2008 г.) ^[1] был венгерским математиком и учёным-компьютерщиком , который специализировался на комбинаторной геометрии и комбинаторной теории множеств . Он, возможно, наиболее известен своей работой в области, которая в конечном итоге будет называться аддитивной комбинаторикой . Особенно примечательным было его «гениальное» ^[2] применение теоремы Семереди–Троттера для улучшения лучшей известной нижней границы для задачи суммы-произведения . ^[3] Он также доказал, что любой алгоритм полиномиального времени, аппроксимирующий объём выпуклых тел, должен иметь мультипликативную ошибку , и ошибка растёт экспоненциально по размерности. ^[4] Совместно с Михой Шариром он создал структуру, которая в конечном итоге привела Гута и Каца к решению проблемы различных расстояний Эрдёша . ^[5] (См. ниже.)

После окончания математической программы в Fazekas Mihály Gimnázium (т. е. « средняя школа Fazekas Mihály » в Будапеште , которая известна своим превосходством, особенно в математике), Элекеш изучал математику в Университете Этвеша Лоранда . После получения степени он присоединился к факультету на кафедре анализа в университете. В 1984 году он присоединился к недавно сформированной кафедре компьютерных наук , которую возглавлял Ласло Ловас . Элекеш был повышен до должности полного профессора в 2005 году. Он получил звание доктора математических наук от Венгерской академии наук в 2001 году. ^[1]

Элекеш начал свою математическую работу в области комбинаторной теории множеств , отвечая на некоторые вопросы, поставленные Эрдёшем и Хайналом . Один из его результатов гласит, что если множество бесконечных подмножеств множества натуральных чисел разбить на счетное множество частей, то в одной из них существует решение уравнения A ∪ B = C. ^{[1] [6]} Позже его интерес переключился на другую любимую тему Эрдёша — дискретную геометрию и геометрическую теорию алгоритмов . В 1986 году он доказал, что если детерминированный полиномиальный алгоритм вычисляет число V ( K ) для каждого выпуклого тела K в любом евклидовом пространстве, заданном оракулом разделения, таким образом, что V ( K ) всегда не меньше vol( K ), объема K , то для каждого достаточно большого измерения n , существует выпуклое тело в n -мерном евклидовом пространстве такое, что V ( K )>2 ^{0,99 n} vol( K ). То есть, любая оценка объема по полиномиальному времени по K должна быть неточной по крайней мере в экспоненциальный раз. ^{[1] [4]}

Незадолго до своей смерти он разработал новые инструменты в алгебраической геометрии и использовал их для получения результатов в дискретной геометрии , доказав гипотезу Пёрди . Миха Шарир организовал, расширил и опубликовал посмертные заметки Элекеса об этих методах. ^[7] Затем Нец Кац и Ларри Гут использовали их для решения (за исключением множителя (log n) ^1/2 ) задачи Эрдёша о различных расстояниях , поставленной в 1946 году. ^{[5] [8]}

• Домашняя страница Элекеса