Майкл Сакс (математик)
Майкл Эзра Сакс — американский математик. В настоящее время он является заведующим кафедрой математики в Университете Рутгерса (2017–), а с 2006 по 2010 год был директором аспирантуры по математике в Университете Рутгерса . Сакс получил докторскую степень. из Массачусетского технологического института в 1980 году после защиты диссертации на тему « Свойства двойственности систем конечных множеств». [1] под руководством его советника Дэниела Дж. Клейтмана .
Список его публикаций и сотрудничества можно найти на сайте DBLP . [2]
В 2016 году он стал членом Ассоциации вычислительной техники . [3] [4]
Исследовать
[ редактировать ]Исследования Сакса в области теории сложности вычислений , комбинаторики и теории графов способствовали изучению нижних границ в теории порядка , рандомизированных вычислениях и пространственно-временном компромиссе .
В 1984 году Сакс и Джефф Кан показали, что существует точная нижняя граница теории информации для сортировки частично упорядоченной информации с точностью до мультипликативной константы. [5]
В [1] была доказана первая суперлинейная нижняя оценка для задачи зашумленного вещания . В модели шумного вещания процессоры назначаются локальный входной бит . Каждый процессор может выполнять шумную широковещательную рассылку всем остальным процессорам, при этом полученные биты могут быть независимо инвертированы с фиксированной вероятностью. Проблема в процессоре определить для какой-то функции . Сакс и др. показал, что существующий протокол Галлагера действительно был оптимальным за счет сокращения обобщенного зашумленного дерева решений , и дал нижняя граница глубины дерева, которое изучает входные данные. [6]
В 2003 году П. Бим, Сакс, К. Сан и Э. Ви опубликовали первый компромисс между нижней границей времени и пространства для рандомизированного вычисления задач принятия решений. [7]
Позиции
[ редактировать ]Сакс занимает должности в редакциях следующих журналов:
- SIAM Journal on Computing , заместитель редактора
- Комбинаторика , член редколлегии
- Журнал теории графов , член редколлегии
- Дискретная прикладная математика , член редколлегии
Избранные публикации
[ редактировать ]- Бородин, Аллан; Линиал, Натан; Сакс, Майкл Э. (1 октября 1992 г.). «Оптимальный онлайн-алгоритм для метрической системы задач» . Журнал АКМ . 39 (4): 745–763. дои : 10.1145/146585.146588 . ISSN 0004-5411 . S2CID 18783826 .
- Фредман, М.; Сакс, М. (1 февраля 1989 г.). «Сложность клеточного зондирования динамических структур данных». Материалы двадцать первого ежегодного симпозиума ACM по теории вычислений - STOC '89 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 345–354. дои : 10.1145/73007.73040 . ISBN 978-0-89791-307-2 . S2CID 13470414 .
- Патури, Рамамохан; Пудлак, Павел; Сакс, Майкл Э.; Зейн, Фрэнсис (1 мая 2005 г.). «Улучшенный алгоритм экспоненциального времени для k-SAT» . Журнал АКМ . 52 (3): 337–364. дои : 10.1145/1066100.1066101 . ISSN 0004-5411 .
- Гольдберг, Эндрю В.; Хартлайн, Джейсон Д.; Карлин, Анна Р.; Сакс, Майкл; Райт, Эндрю (1 мая 2006 г.). «Конкурсные аукционы» . Игры и экономическое поведение . Мини-спецвыпуск: Дизайн электронного рынка. 55 (2): 242–269. дои : 10.1016/j.geb.2006.02.003 . ISSN 0899-8256 .
- Сакс, Майкл; Захароглу, Фотиос (1 января 2000 г.). «Соглашение о k-множестве без ожидания невозможно: топология общедоступных знаний» . SIAM Journal по вычислительной технике . 29 (5): 1449–1483. дои : 10.1137/S0097539796307698 . ISSN 0097-5397 .
- Сакс, Майкл; Вигдерсон, Ави (октябрь 1986 г.). «Вероятностные логические деревья решений и сложность оценки игровых деревьев» . 27-й ежегодный симпозиум по основам информатики (SFCS, 1986) . стр. 29–38. дои : 10.1109/SFCS.1986.44 . ISBN 0-8186-0740-8 . S2CID 6130392 .
- Сакс, Майкл; Ю, Лан (5 июня 2005 г.). «Для истинности в выпуклых областях достаточно слабой монотонности» . Материалы 6-й конференции ACM по электронной коммерции . ЕС '05. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 286–293. дои : 10.1145/1064009.1064040 . ISBN 978-1-59593-049-1 . S2CID 2135397 .
Ссылки
[ редактировать ]- ^ Сакс, Майкл Эзра (1980). Свойства двойственности систем конечных множеств (кандидатская диссертация). Массачусетский технологический институт . OCLC 7447661 .
- ^ Майкл Э. Сакс на DBLP библиографическом сервере
- ^ Сотрудники Cacm (март 2017 г.), «ACM признает новых сотрудников», Сообщения ACM , 60 (3): 23, doi : 10.1145/3039921 , S2CID 31701275 .
- ^ «Получатели» . Награды.acm.org . Проверено 1 июля 2018 г.
- ^ Кан, Дж.; Сакс, М. (1984). «Каждый посет имеет хорошее сравнение». Материалы шестнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '84 . п. 299. дои : 10.1145/800057.808694 . ISBN 978-0897911337 . S2CID 17374296 .
- ^ Галлагер, Р.Г. (1988). «Нахождение паритета в простых сетях вещания». Транзакции IEEE по теории информации . 34 (2): 176–180. CiteSeerX 10.1.1.422.3311 . дои : 10.1109/18.2626 .
- ^ Бим, П.; Сакс, М.; Солнце, Х.; Ви, Э. (2003). «Нижние границы компромисса между временем и пространством для рандомизированного вычисления задач принятия решений». Журнал АКМ . 50 (2): 154. CiteSeerX 10.1.1.16.8696 . дои : 10.1145/636865.636867 . S2CID 9459178 .
