Майкл Сакс (математик)

американский математик

Майкл Эзра Сакс — американский математик. В настоящее время он является заведующим кафедрой математического факультета Ратгерского университета (2017–) и с 2006 по 2010 год был директором аспирантуры по математике в Ратгерском университете . Сакс получил степень доктора философии в Массачусетском технологическом институте в 1980 году после завершения диссертации под названием « Свойства дуальности систем конечных множеств» ^[1] под руководством Дэниела Дж. Клейтмана .

Список его публикаций и совместных работ можно найти на сайте DBLP . ^[2]

В 2016 году он стал членом Ассоциации вычислительной техники . ^{[3] [4]}

Исследовать

Исследования Сакса в области теории сложности вычислений , комбинаторики и теории графов внесли вклад в изучение нижних границ в теории порядка , рандомизированных вычислений и компромисса между пространством и временем .

В 1984 году Сакс и Джефф Кан показали, что существует точная нижняя граница теории информации для сортировки при частично упорядоченной информации с точностью до мультипликативной константы. ^[5]

В [1] была доказана первая суперлинейная нижняя граница для проблемы шумной трансляции. В модели шумной трансляции процессорам назначается локальный входной бит . Каждый процессор может выполнять шумную трансляцию всем другим процессорам, где полученные биты могут быть независимо перевернуты с фиксированной вероятностью. Проблема заключается в том, чтобы процессор определил для некоторой функции . Сакс и др. показали, что существующий протокол Галлагера действительно был оптимальным путем редукции из обобщенного шумного дерева решений и вывел нижнюю границу для глубины дерева, которое изучает входные данные. ^[6] ${\displaystyle n+1}$ ${\displaystyle P_{0},P_{1},\ldots ,P_{n}}$ ${\displaystyle x_{i}}$ ${\displaystyle P_{0}}$ ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle f}$ ${\displaystyle \Omega (n\log(n))}$

В 2003 году П. Бим, Сакс, X. Сан и Э. Ви опубликовали первую работу, в которой было доказано, что нижняя граница компромисса между временем и пространством для рандомизированных вычислений задач принятия решений ^{[7] .}

Позиции

Сакс занимает должности в следующих редколлегиях журналов:

• Журнал SIAM по вычислительной технике , заместитель редактора
• Combinatorica , член редколлегии
• Журнал теории графов , член редколлегии
• Дискретная прикладная математика , член редколлегии

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

• Бородин, Аллан; Линиал, Натан; Сакс, Майкл Э. (1992-10-01). «Оптимальный онлайн-алгоритм для метрической системы задач». Журнал ACM . 39 (4): 745–763. doi : 10.1145/146585.146588 . ISSN  0004-5411. S2CID  18783826.
• Фредман, М.; Сакс, М. (1989-02-01). "Сложность зонда ячейки динамических структур данных". Труды двадцать первого ежегодного симпозиума ACM по теории вычислений - STOC '89 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 345–354. doi : 10.1145/73007.73040 . ISBN 978-0-89791-307-2. S2CID  13470414.
• Патури, Рамамохан; Пудлак, Павел; Сакс, Майкл Э.; Зейн, Фрэнсис (01.05.2005). «Улучшенный алгоритм экспоненциального времени для k-SAT». Журнал ACM . 52 (3): 337–364. doi :10.1145/1066100.1066101. ISSN  0004-5411.
• Голдберг, Эндрю В.; Хартлайн, Джейсон Д.; Карлин, Анна Р.; Сакс, Майкл; Райт, Эндрю (2006-05-01). «Конкурентные аукционы». Игры и экономическое поведение . Мини-спецвыпуск: Электронный рыночный дизайн. 55 (2): 242–269. doi :10.1016/j.geb.2006.02.003. ISSN  0899-8256.
• Сакс, Майкл; Захароглу, Фотиос (2000-01-01). «Соглашение о k-множестве без ожидания невозможно: топология общедоступных знаний». Журнал SIAM по вычислениям . 29 (5): 1449–1483. doi :10.1137/S0097539796307698. ISSN  0097-5397.
• Сакс, Майкл; Вигдерсон, Ави (октябрь 1986 г.). «Вероятностные булевы деревья решений и сложность оценки игровых деревьев». 27-й ежегодный симпозиум по основам компьютерной науки (SFCS 1986) . стр. 29–38. doi :10.1109/SFCS.1986.44. ISBN 0-8186-0740-8. S2CID  6130392.
• Сакс, Майкл; Ю, Лан (2005-06-05). «Слабая монотонность достаточна для истинности в выпуклых областях». Труды 6-й конференции ACM по электронной коммерции . EC '05. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 286–293. doi :10.1145/1064009.1064040. ISBN 978-1-59593-049-1. S2CID  2135397.

Ссылки

1. Сакс, Майкл Эзра (1980). Свойства двойственности систем конечных множеств (диссертация). Массачусетский технологический институт . OCLC  7447661.
2. Майкл Э. Сакс на сервере библиографии DBLP
3. Сотрудники Cacm (март 2017 г.), «ACM признаёт новых стипендиатов», Сообщения ACM , 60 (3): 23, doi : 10.1145/3039921, S2CID  31701275.
4. "Получатели". awards.acm.org . Получено 2018-07-01 .
5. Кан, Дж.; Сакс, М. (1984). "Каждый посет имеет хорошее сравнение". Труды шестнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '84 . стр. 299. doi :10.1145/800057.808694. ISBN 978-0897911337. S2CID  17374296.
6. Галлагер, РГ (1988). «Нахождение паритета в простых широковещательных сетях». Труды IEEE по теории информации . 34 (2): 176–180. CiteSeerX 10.1.1.422.3311 . doi :10.1109/18.2626. 
7. Beame, P.; Saks, M.; Sun, X.; Vee, E. (2003). "Нижние границы компромисса между временем и пространством для рандомизированных вычислений задач принятия решений". Journal of the ACM . 50 (2): 154. CiteSeerX 10.1.1.16.8696 . doi :10.1145/636865.636867. S2CID  9459178. 

Внешние ссылки

• Майкл Эзра Сакс в проекте «Генеалогия математики »