Майкл Сакс (математик) - Michael Saks (mathematician)

Майкл Эзра Сакс американский математик. В настоящее время он является заведующим кафедрой математики в Университете Рутгерса (2017-), а с (2006–2010 гг.) Был директором программы для выпускников математики в Университет Рутгерса. Сакс получил докторскую степень. от Массачусетский Институт Технологий в 1980 году после защиты диссертации Свойства двойственности систем конечных множеств[1] под его советником Дэниел Дж. Клейтман.

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

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

Исследование

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

В Kahn and Saks (1984) было показано, что существует точная теоретико-информационная нижняя граница для сортировки при частично заказанный информация с точностью до мультипликативной постоянной.[5]

В [1] первая суперлинейная нижняя оценка проблема с шумной трансляцией было доказано. В шумной модели вещания процессоры назначается локальный входной бит . Каждый процессор может выполнять шумная трансляция ко всем остальным процессорам, где полученные биты могут быть независимо перевернуты с фиксированной вероятностью. Проблема в процессоре определить для какой-то функции . Saks et al. показал, что существующий протокол Галлагера действительно был оптимальным путем сокращения от обобщенного зашумленного Древо решений и произвел нижняя граница глубины дерева, которое изучает ввод.[6]

В Beame et al. (2003) был доказан первый компромисс между временной и пространственной нижней границей для рандомизированного вычисления задач принятия решений.[7]

Позиции

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

  • SIAM J. on Computing, младший редактор
  • Combinatorica, член редколлегии
  • Журнал теории графов, член редколлегии
  • Дискретная прикладная математика, член редколлегии

Рекомендации

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

внешняя ссылка