バージニア・ヴァシレフスカ・ウィリアムズ

バージニア・ヴァシレフスカ・ウィリアムズ
バージニア・ヴァシレフスカ・ウィリアムズ
	ヴァシレフスカ・ウィリアムズ、オーバーヴォルフアッハにて、2012年
国籍	ブルガリア系アメリカ人
母校	カーネギーメロン大学（博士号、2008年）; カリフォルニア工科大学 (BS, 2003);
知られている	行列の乗算; グラフアルゴリズム; 動的アルゴリズム; 細粒度複雑性理論;
	科学者としてのキャリア
フィールド	複雑性理論; アルゴリズム;
機関	マサチューセッツ工科大学; スタンフォード; カリフォルニア大学バークレー校; 高等研究所;
博士課程の指導教員	ガイ・ブレロック

ヴァージニア・ヴァシレフスカ・ウィリアムズ（旧姓ヴァージニア・パナヨトヴァ・ヴァシレフスカ）^[1]は、計算複雑性理論とアルゴリズムの研究で知られる理論計算機科学者および数学者です。現在はマサチューセッツ工科大学のスティーブン・アンド・ルネ・フィンキャリア開発准教授で、電気工学および計算機科学を担当しています。^{[2]彼女は、}高速行列乗算における画期的な成果^[3]、動的アルゴリズムに関する研究^[4]、および細粒度複雑性の分野の発展に貢献したことで知られています。^[5]

教育とキャリア

ウィリアムズはブルガリア出身で、ソフィアのドイツ語高校に通っていました。^{[6] 2003年に}カリフォルニア工科大学を卒業し、2008年にカーネギーメロン大学で博士号を取得しました。 ^[1]彼女の博士論文「重み付きグラフの経路問題に対する効率的なアルゴリズム」はガイ・ブレロックの指導を受けました。^[7]

ウィリアムズは、カリフォルニア大学バークレー校高等研究所で博士研究員として研究を行った後、 2013年にスタンフォード大学のコンピューターサイエンスの助教授に就任しました。 ^[1]彼女は2017年にMITに准教授として移りました。^[2]

研究

2011年、ウィリアムズは2つの行列を時間内に掛け算するアルゴリズムを発見した。これは、24年間最もよく知られていた行列乗算アルゴリズムの時間制限であるコッパースミス・ウィノグラードアルゴリズムを改良した。彼女の最初の改良はアンドリュー・ストザースとは独立しており、ストザースも1年前に同じ制限を改善していた。彼女はストザースの研究を知った後、両方の方法のアイデアを組み合わせて彼の制限も改善した。^[8]^[3] 2023年現在、彼女の研究は共同研究者とともに、時間内に行列乗算を行う現在の最もよく知られたアルゴリズムを確立している。^[9]^[10] $n\times n$ $O(n^{2.373})$ $O(n^{2.371552})$

認識

ウィリアムズは2009年から2011年までNSFコンピューティングイノベーションフェローを務め、^[1] 2017年にはスローン研究フェローシップを受賞しました。 ^{[2]彼女は2018年の}国際数学者会議に招待講演者として招待され、コンピュータサイエンスの数学的側面のセクションで講演しました。^[11]

私生活

ウィリアムズは応用数学者のパナヨット・ヴァシレフスキーとタニヤ・コストヴァ・ヴァシレフスカの娘である。^{[12]彼女は同じくMITのコンピュータサイエンス教授である}ライアン・ウィリアムズと結婚しており、2人は細粒度複雑性の分野で協力している。^[6]

参考文献

^ abcd 履歴書(PDF) 、 2018年2月24日取得
^ abc 3人のEECS教授が2017年度スローン研究フェローシップを受賞、マサチューセッツ工科大学電気工学・コンピュータサイエンス学部、2017年2月22日、2018年3月22日時点のオリジナルよりアーカイブ、 2018年2月25日閲覧
^ ab Virginia Vassilevska Williams (2012)、「Coppersmith-Winograd より高速な行列乗算」、Howard J. Karloff および Toniann Pitassi (編)、Proceedings of the 44th Symposium on Theory of Computing (STOC)、ACM、pp. 887–898、CiteSeerX 10.1.1.297.2680、doi :10.1145/2213977.2214056、ISBN 978-1-4503-1245-5、S2CID 14350287
^ Abboud, Amir; Williams, Virginia Vassilevska (2014)、「一般的な推測は動的問題に対する強い下限を暗示する」、2014 IEEE 55th Annual Symposium on Foundations of Computer Science、pp. 434–443、arXiv : 1402.0054、doi :10.1109/FOCS.2014.53、ISBN 978-1-4799-6517-5、S2CID 2267837
^ ウィリアムズ、VV（2019）、「アルゴリズムと複雑性に関するいくつかの細粒度の質問について」、国際数学者会議（ICM 2018）の議事録：3447–3487、doi：10.1142 / 9789813272880_0188、ISBN 978-981-327-287-3、S2CID 19282287
^ ab マセソン、ロブ（2020年1月7日）、「アルゴリズムの真の可能性を見つける：数学理論を使用して、バージニアウィリアムズはアルゴリズムをより速く実行するように誘導し、アルゴリズムが最大速度に達したことを証明する」、MITニュース、 2021年12月18日取得
^ 数学系譜プロジェクトのバージニア・ヴァシレフスカ・ウィリアムズ
^ アロン、ジェイコブ（2011年12月9日）「重要な数学ツールが24年ぶりに進歩」、ニューサイエンティスト
^ ウィリアムズ、バージニア・ヴァシレフスカ; 徐、銀山; 徐、子玄; 周、人飛 (2023 年 7 月 16 日)、行列乗算の新しい境界: アルファからオメガへ、arXiv : 2307.07970
^ 「新たなブレークスルーにより行列乗算が理想に近づく」、Quanta Magazine、2024年3月7日、2024年3月8日閲覧
^ 「Speakers」、ICM 2018、2017年12月15日時点のオリジナルよりアーカイブ、2018年2月24日閲覧
^ 「ヴァシレフスカとウィリアムズが結婚」、エンゲージメント、ハーツェル・エンクワイラー、2008年8月28日、 2022年7月10日閲覧。

外部リンク

ホームページ
Google Scholarに索引付けされた Virginia Vassilevska Williams の出版物
DBLP書誌サーバーの Virginia Vassilevska Williams

[cv-1] 履歴書(PDF) 、 2018年2月24日取得

[sloan-2] 3人のEECS教授が2017年度スローン研究フェローシップを受賞、マサチューセッツ工科大学電気工学・コンピュータサイエンス学部、2017年2月22日、2018年3月22日時点のオリジナルよりアーカイブ、 2018年2月25日閲覧

[stoc-3] Virginia Vassilevska Williams (2012)、「Coppersmith-Winograd より高速な行列乗算」、Howard J. Karloff および Toniann Pitassi (編)、Proceedings of the 44th Symposium on Theory of Computing (STOC)、ACM、pp. 887–898、CiteSeerX 10.1.1.297.2680、doi :10.1145/2213977.2214056、ISBN 978-1-4503-1245-5、S2CID 14350287

[dynamiclowerbounds-4] Abboud, Amir; Williams, Virginia Vassilevska (2014)、「一般的な推測は動的問題に対する強い下限を暗示する」、2014 IEEE 55th Annual Symposium on Foundations of Computer Science、pp. 434–443、arXiv : 1402.0054、doi :10.1109/FOCS.2014.53、ISBN 978-1-4799-6517-5、S2CID 2267837

[finegrained-5] ウィリアムズ、VV（2019）、「アルゴリズムと複雑性に関するいくつかの細粒度の質問について」、国際数学者会議（ICM 2018）の議事録：3447–3487、doi：10.1142 / 9789813272880_0188、ISBN 978-981-327-287-3、S2CID 19282287

[true-6] マセソン、ロブ（2020年1月7日）、「アルゴリズムの真の可能性を見つける：数学理論を使用して、バージニアウィリアムズはアルゴリズムをより速く実行するように誘導し、アルゴリズムが最大速度に達したことを証明する」、MITニュース、 2021年12月18日取得

[mgp-7] 数学系譜プロジェクトのバージニア・ヴァシレフスカ・ウィリアムズ

[ns-8] アロン、ジェイコブ（2011年12月9日）「重要な数学ツールが24年ぶりに進歩」、ニューサイエンティスト

[matrix2023-9] ウィリアムズ、バージニア・ヴァシレフスカ; 徐、銀山; 徐、子玄; 周、人飛 (2023 年 7 月 16 日)、行列乗算の新しい境界: アルファからオメガへ、arXiv : 2307.07970

[quanta2024-10] 「新たなブレークスルーにより行列乗算が理想に近づく」、Quanta Magazine、2024年3月7日、2024年3月8日閲覧

[icm-11] 「Speakers」、ICM 2018、2017年12月15日時点のオリジナルよりアーカイブ、2018年2月24日閲覧

[engage-12] 「ヴァシレフスカとウィリアムズが結婚」、エンゲージメント、ハーツェル・エンクワイラー、2008年8月28日、 2022年7月10日閲覧。