Вирджиния Василевска Уильямс

Вирджиния Василевска Уильямс
Вирджиния Василевска Уильямс
	Василевска Уильямс в Обервольфахе , 2012 г.
Национальность	Болгарский американец
Альма-матер	Университет Карнеги-Меллона (доктор философии, 2008 г.) ; Калифорнийский технологический институт (бакалавр наук, 2003 г.) ;
Известный	Умножение матрицы ; Графовые алгоритмы ; Динамические алгоритмы ; Детализированная теория сложности ;
	Научная карьера
Поля	Теория сложности ; Алгоритмы ;
Учреждения	С ; Стэнфорд ; Калифорнийский университет в Беркли ; Институт перспективных исследований ;
Докторантура	Гай Блеллок

Вирджиния Василевска Уильямс (урожденная Вирджиния Панайотова Василевска) ^[1] — ученый-теоретик и математик, известный своими исследованиями в области теории сложности вычислений и алгоритмов . В настоящее время она является доцентом кафедры электротехники и информатики Стивена и Рене Финн по развитию карьеры в Массачусетском технологическом институте . ^[2] Она известна своими прорывными результатами в быстром умножении матриц . ^[3] за работу над динамическими алгоритмами , ^[4] и за помощь в разработке области мелкозернистой сложности . ^[5]

Образование и карьера

Уильямс родом из Болгарии и посещал немецкоязычную среднюю школу в Софии . ^[6] В 2003 году она окончила Калифорнийский технологический институт и защитила докторскую диссертацию. в Университете Карнеги-Меллона в 2008 году. ^[1] Ее диссертацию « Эффективные алгоритмы решения задач пути во взвешенных графах » курировал Гай Блеллок . ^[7]

После докторской диссертации в Институте перспективных исследований и Калифорнийском университете в Беркли Уильямс в 2013 году стал доцентом кафедры информатики в Стэнфордском университете . ^[1] В 2017 году она переехала в Массачусетский технологический институт в качестве доцента. ^[2]

Исследовать

В 2011 году Уильямс нашел алгоритм умножения двух $n\times n$ матрицы во времени $O(n^{2.373})$ . Это улучшило предыдущую оценку времени для алгоритмов умножения матриц , алгоритма Копперсмита-Винограда , который считался самым известным в течение 24 лет. Ее первоначальное улучшение не зависело от Эндрю Стотерса, который также улучшил тот же результат годом ранее; узнав о работе Стотерса, она объединила идеи обоих методов, чтобы улучшить и его оценку. ^[8]^[3] По состоянию на 2023 год в ее работе вместе с ее сотрудниками также будет установлен самый известный на данный момент алгоритм умножения матриц. $O(n^{2.371552})$ . ^[9]^[10]

Признание

Уильямс был научным сотрудником NSF в области компьютерных инноваций в 2009–2011 годах. ^[1] и выиграл исследовательскую стипендию Слоана в 2017 году. ^[2] Она была приглашенным докладчиком на Международном конгрессе математиков 2018 года , выступая в секции «Математические аспекты информатики». ^[11]

Личная жизнь

Уильямс — дочь математиков-прикладников Панайота Василевского и Тани Костовой-Василевской. ^[12] Она замужем за Райаном Уильямсом , также профессором информатики в Массачусетском технологическом институте; они вместе работали в области мелкозернистой сложности . ^[6]

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Биографические данные (PDF) , получено 24 февраля 2018 г.
^ Перейти обратно: ^а ^б ^с Три профессора EECS получили исследовательские стипендии Слоана в 2017 году , Департамент электротехники и информатики Массачусетского технологического института, 22 февраля 2017 г., заархивировано из оригинала 22 марта 2018 г. , получено 25 февраля 2018 г.
^ Перейти обратно: ^а ^б Вирджиния Василевска Уильямс (2012), «Умножение матриц быстрее, чем Копперсмит-Виноград», в книге Ховарда Дж. Карлоффа и Тонианн Питасси (ред.), Труды 44-го симпозиума по теории вычислений (STOC) , ACM, стр. 887–898. , CiteSeerX 10.1.1.297.2680 , doi : 10.1145/2213977.2214056 , S2CID 14350287
^ Аббуд, Амир; Уильямс, Вирджиния Василевска (2014), «Популярные гипотезы подразумевают сильные нижние границы для динамических задач», 55-й ежегодный симпозиум IEEE по основам информатики , 2014 г., стр. 434–443, arXiv : 1402.0054 , doi : 10.1109/FOCS.2014.53 , ISBN 978-1-4799-6517-5 , S2CID 2267837
^ Уильямс, В.В. (2019), «О некоторых детальных вопросах алгоритмов и сложности», Труды Международного конгресса математиков (ICM 2018) : 3447–3487, doi : 10.1142/9789813272880_0188 , ISBN 978-981-327-287-3 , S2CID 19282287
^ Перейти обратно: ^а ^б Мэтисон, Роб (7 января 2020 г.), «Обнаружение истинного потенциала алгоритмов: используя математическую теорию, Вирджиния Уильямс уговаривает алгоритмы работать быстрее или доказывает, что они достигли максимальной скорости» , MIT News , получено 18 декабря 2021 г.
^ Вирджиния Василевска Уильямс в проекте «Математическая генеалогия»
^ Арон, Джейкоб (9 декабря 2011 г.), «Ключевой математический инструмент впервые за 24 года продвинулся вперед» , New Scientist
^ Уильямс, Вирджиния Василевска; Сюй, Иньчжан; Сюй, Цзысюань; Чжоу, Жэньфэй (16 июля 2023 г.), «Новые границы умножения матриц: от альфы до омеги» , arXiv.org , получено 6 марта 2024 г.
^ «Новый прорыв приближает умножение матриц к идеалу» , Quanta Magazine , 7 марта 2024 г. , получено 8 марта 2024 г.
^ «Speakers» , ICM 2018 , заархивировано из оригинала 15 декабря 2017 г. , получено 24 февраля 2018 г.
^ «Васильевская и Уильямс выходят замуж» , Помолвки , Hartselle Enquirer , 28 августа 2008 г. , получено 10 июля 2022 г.

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

Домашняя страница
Публикации Вирджинии Василевской Уильямс, проиндексированные Google Scholar
Вирджиния Василевска Уильямс на DBLP библиографическом сервере

[cv-1] Перейти обратно: ^а ^б ^с ^д Биографические данные (PDF) , получено 24 февраля 2018 г.

[sloan-2] Перейти обратно: ^а ^б ^с Три профессора EECS получили исследовательские стипендии Слоана в 2017 году , Департамент электротехники и информатики Массачусетского технологического института, 22 февраля 2017 г., заархивировано из оригинала 22 марта 2018 г. , получено 25 февраля 2018 г.

[stoc-3] Перейти обратно: ^а ^б Вирджиния Василевска Уильямс (2012), «Умножение матриц быстрее, чем Копперсмит-Виноград», в книге Ховарда Дж. Карлоффа и Тонианн Питасси (ред.), Труды 44-го симпозиума по теории вычислений (STOC) , ACM, стр. 887–898. , CiteSeerX 10.1.1.297.2680 , doi : 10.1145/2213977.2214056 , S2CID 14350287

[dynamiclowerbounds-4] Аббуд, Амир; Уильямс, Вирджиния Василевска (2014), «Популярные гипотезы подразумевают сильные нижние границы для динамических задач», 55-й ежегодный симпозиум IEEE по основам информатики , 2014 г., стр. 434–443, arXiv : 1402.0054 , doi : 10.1109/FOCS.2014.53 , ISBN 978-1-4799-6517-5 , S2CID 2267837

[finegrained-5] Уильямс, В.В. (2019), «О некоторых детальных вопросах алгоритмов и сложности», Труды Международного конгресса математиков (ICM 2018) : 3447–3487, doi : 10.1142/9789813272880_0188 , ISBN 978-981-327-287-3 , S2CID 19282287

[true-6] Перейти обратно: ^а ^б Мэтисон, Роб (7 января 2020 г.), «Обнаружение истинного потенциала алгоритмов: используя математическую теорию, Вирджиния Уильямс уговаривает алгоритмы работать быстрее или доказывает, что они достигли максимальной скорости» , MIT News , получено 18 декабря 2021 г.

[mgp-7] Вирджиния Василевска Уильямс в проекте «Математическая генеалогия»

[ns-8] Арон, Джейкоб (9 декабря 2011 г.), «Ключевой математический инструмент впервые за 24 года продвинулся вперед» , New Scientist

[matrix2023-9] Уильямс, Вирджиния Василевска; Сюй, Иньчжан; Сюй, Цзысюань; Чжоу, Жэньфэй (16 июля 2023 г.), «Новые границы умножения матриц: от альфы до омеги» , arXiv.org , получено 6 марта 2024 г.

[quanta2024-10] «Новый прорыв приближает умножение матриц к идеалу» , Quanta Magazine , 7 марта 2024 г. , получено 8 марта 2024 г.

[icm-11] «Speakers» , ICM 2018 , заархивировано из оригинала 15 декабря 2017 г. , получено 24 февраля 2018 г.

[engage-12] «Васильевская и Уильямс выходят замуж» , Помолвки , Hartselle Enquirer , 28 августа 2008 г. , получено 10 июля 2022 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]