33:
343:, that had stood as the best known for 24 years. Her initial improvement was independent of Andrew Stothers, who also improved the same bound a year earlier; after learning of Stothers' work, she combined ideas from both methods to improve his bound as well. As of 2023, her work also establishes the current best-known algorithm for matrix multiplication with her collaborators, in time
460:
377:
333:
297:
630:"Finding the true potential of algorithms: Using mathematical theory, Virginia Williams coaxes algorithms to run faster or proves they've hit their maximum speed"
882:
857:
90:
466:
387:
Williams was an NSF Computing
Innovation Fellow for 2009–2011, and won a Sloan Research Fellowship in 2017. She was an invited speaker at the 2018
837:
489:
Virginia
Vassilevska Williams (2012), "Multiplying Matrices Faster than Coppersmith-Winograd", in Howard J. Karloff and Toniann Pitassi (ed.),
38:
877:
832:
202:. She is currently the Steven and Renee Finn Career Development Associate Professor of Electrical Engineering and Computer Science at the
847:
709:
668:
872:
862:
465:, Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science, February 22, 2017, archived from
852:
388:
842:
827:
602:
562:
203:
149:
867:
733:
533:
Abboud, Amir; Williams, Virginia
Vassilevska (2014), "Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems",
399:
Williams is the daughter of applied mathematicians
Panayot Vassilevski and Tanya Kostova-Vassilevska. She is married to
400:
340:
258:
235:
207:
159:
71:
194:(née Virginia Panayotova Vassilevska) is a theoretical computer scientist and mathematician known for her research in
492:
336:
195:
128:
655:
254:
211:
164:
100:
239:
63:
346:
503:
302:
32:
822:
498:
404:
276:
215:
105:
629:
761:
8:
793:
262:
154:
50:
685:
Williams, Virginia
Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei (July 16, 2023),
608:
585:
Williams, V. V. (2019), "On Some Fine-Grained
Questions in Algorithms and Complexity",
568:
540:
516:
403:, also a computer science professor at MIT; they have worked together in the field of
598:
558:
612:
520:
590:
572:
550:
508:
174:
95:
741:
797:
594:
534:
431:
816:
651:
512:
247:
179:
554:
391:, speaking in the section on Mathematical Aspects of Computer Science.
199:
133:
788:
587:
Proceedings of the
International Congress of Mathematicians (ICM 2018)
686:
227:
545:
536:
2014 IEEE 55th Annual
Symposium on Foundations of Computer Science
261:, Williams became an assistant professor of computer science at
802:
710:"New Breakthrough Brings Matrix Multiplication Closer to Ideal"
488:
462:
Three EECS professors receive 2017 Sloan
Research Fellowships
265:
in 2013. She moved to MIT as an associate professor in 2017.
231:
806:
687:"New Bounds for Matrix Multiplication: from Alpha to Omega"
273:
In 2011, Williams found an algorithm for multiplying two
244:
Efficient
Algorithms for Path Problems in Weighted Graphs
669:"Key mathematical tool sees first advance in 24 years"
349:
305:
279:
371:
327:
291:
526:
206:. She is notable for her breakthrough results in
814:
684:
230:, and attended a German-language high school in
532:
883:21st-century American women mathematicians
702:
578:
335:. This improved a previous time bound for
214:, and for helping to develop the field of
31:
858:California Institute of Technology alumni
678:
544:
502:
627:
584:
389:International Congress of Mathematicians
455:
453:
451:
221:
815:
754:
623:
621:
484:
482:
838:21st-century Bulgarian mathematicians
204:Massachusetts Institute of Technology
878:American people of Bulgarian descent
833:21st-century American mathematicians
666:
448:
426:
424:
422:
420:
238:in 2003, and completed her Ph.D. at
726:
618:
479:
253:After postdoctoral research at the
13:
848:American women computer scientists
645:
259:University of California, Berkeley
236:California Institute of Technology
14:
894:
873:MIT School of Engineering faculty
863:Carnegie Mellon University alumni
782:
660:
628:Matheson, Rob (January 7, 2020),
417:
667:Aron, Jacob (December 9, 2011),
493:Symposium on Theory of Computing
394:
337:matrix multiplication algorithms
853:Theoretical computer scientists
372:{\displaystyle O(n^{2.371552})}
196:computational complexity theory
843:Bulgarian women mathematicians
762:"Vassilevska, Williams to wed"
382:
366:
353:
341:Coppersmith–Winograd algorithm
322:
309:
106:Fine-grained complexity theory
16:Theoretical computer scientist
1:
803:Virginia Vassilevska Williams
794:Virginia Vassilevska Williams
656:Mathematics Genealogy Project
652:Virginia Vassilevska Williams
410:
192:Virginia Vassilevska Williams
25:Virginia Vassilevska Williams
828:American computer scientists
328:{\displaystyle O(n^{2.373})}
255:Institute for Advanced Study
226:Williams is originally from
165:Institute for Advanced Study
7:
868:Stanford University faculty
268:
242:in 2008. Her dissertation,
10:
899:
595:10.1142/9789813272880_0188
240:Carnegie Mellon University
208:fast matrix multiplication
64:Carnegie Mellon University
497:, ACM, pp. 887–898,
292:{\displaystyle n\times n}
234:. She graduated from the
185:
173:
142:
121:
114:
83:
56:
46:
30:
23:
796:publications indexed by
491:Proceedings of the 44th
37:Vassilevska Williams at
513:10.1145/2213977.2214056
405:fine-grained complexity
216:fine-grained complexity
373:
329:
293:
374:
330:
294:
91:Matrix multiplication
555:10.1109/FOCS.2014.53
539:, pp. 434–443,
347:
303:
277:
246:, was supervised by
222:Education and career
809:Bibliography Server
263:Stanford University
766:Hartselle Enquirer
369:
325:
289:
212:dynamic algorithms
210:, for her work on
101:Dynamic algorithms
51:Bulgarian American
768:, August 28, 2008
604:978-981-327-287-3
564:978-1-4799-6517-5
299:matrices in time
189:
188:
129:Complexity theory
116:Scientific career
890:
776:
775:
774:
773:
758:
752:
751:
750:
749:
740:, archived from
730:
724:
723:
722:
721:
706:
700:
699:
698:
697:
682:
676:
675:
664:
658:
649:
643:
642:
641:
640:
625:
616:
615:
582:
576:
575:
548:
530:
524:
523:
506:
486:
477:
476:
475:
474:
457:
446:
445:
444:
443:
438:
433:Curriculum vitae
428:
378:
376:
375:
370:
365:
364:
334:
332:
331:
326:
321:
320:
298:
296:
295:
290:
175:Doctoral advisor
96:Graph algorithms
76:
68:
35:
21:
20:
898:
897:
893:
892:
891:
889:
888:
887:
813:
812:
785:
780:
779:
771:
769:
764:, Engagements,
760:
759:
755:
747:
745:
732:
731:
727:
719:
717:
716:, March 7, 2024
714:Quanta Magazine
708:
707:
703:
695:
693:
683:
679:
665:
661:
650:
646:
638:
636:
626:
619:
605:
583:
579:
565:
531:
527:
504:10.1.1.297.2680
487:
480:
472:
470:
459:
458:
449:
441:
439:
436:
430:
429:
418:
413:
397:
385:
360:
356:
348:
345:
344:
316:
312:
304:
301:
300:
278:
275:
274:
271:
224:
169:
138:
110:
79:
74:
66:
57:Alma mater
42:
26:
17:
12:
11:
5:
896:
886:
885:
880:
875:
870:
865:
860:
855:
850:
845:
840:
835:
830:
825:
811:
810:
800:
798:Google Scholar
791:
784:
783:External links
781:
778:
777:
753:
725:
701:
677:
659:
644:
617:
603:
577:
563:
525:
478:
447:
415:
414:
412:
409:
396:
393:
384:
381:
368:
363:
359:
355:
352:
324:
319:
315:
311:
308:
288:
285:
282:
270:
267:
223:
220:
187:
186:
183:
182:
177:
171:
170:
168:
167:
162:
157:
152:
146:
144:
140:
139:
137:
136:
131:
125:
123:
119:
118:
112:
111:
109:
108:
103:
98:
93:
87:
85:
84:Known for
81:
80:
78:
77:
69:
60:
58:
54:
53:
48:
44:
43:
36:
28:
27:
24:
15:
9:
6:
4:
3:
2:
895:
884:
881:
879:
876:
874:
871:
869:
866:
864:
861:
859:
856:
854:
851:
849:
846:
844:
841:
839:
836:
834:
831:
829:
826:
824:
823:Living people
821:
820:
818:
808:
804:
801:
799:
795:
792:
790:
787:
786:
767:
763:
757:
744:on 2017-12-15
743:
739:
735:
729:
715:
711:
705:
692:
688:
681:
674:
673:New Scientist
670:
663:
657:
653:
648:
635:
631:
624:
622:
614:
610:
606:
600:
596:
592:
589:: 3447–3487,
588:
581:
574:
570:
566:
560:
556:
552:
547:
542:
538:
537:
529:
522:
518:
514:
510:
505:
500:
496:
494:
485:
483:
469:on 2018-03-22
468:
464:
463:
456:
454:
452:
435:
434:
427:
425:
423:
421:
416:
408:
406:
402:
401:Ryan Williams
395:Personal life
392:
390:
380:
361:
357:
350:
342:
338:
317:
313:
306:
286:
283:
280:
266:
264:
260:
256:
251:
249:
245:
241:
237:
233:
229:
219:
217:
213:
209:
205:
201:
197:
193:
184:
181:
178:
176:
172:
166:
163:
161:
158:
156:
153:
151:
148:
147:
145:
141:
135:
132:
130:
127:
126:
124:
120:
117:
113:
107:
104:
102:
99:
97:
94:
92:
89:
88:
86:
82:
73:
70:
65:
62:
61:
59:
55:
52:
49:
45:
40:
34:
29:
22:
19:
770:, retrieved
765:
756:
746:, retrieved
742:the original
737:
728:
718:, retrieved
713:
704:
694:, retrieved
690:
680:
672:
662:
647:
637:, retrieved
633:
586:
580:
535:
528:
490:
471:, retrieved
467:the original
461:
440:, retrieved
432:
398:
386:
272:
252:
248:Guy Blelloch
243:
225:
191:
190:
180:Guy Blelloch
143:Institutions
115:
18:
383:Recognition
160:UC Berkeley
67:(PhD, 2008)
47:Nationality
39:Oberwolfach
817:Categories
772:2022-07-10
748:2018-02-24
734:"Speakers"
720:2024-03-08
696:2024-03-06
639:2021-12-18
473:2018-02-25
442:2018-02-24
411:References
200:algorithms
134:Algorithms
75:(BS, 2003)
789:Home page
691:arXiv.org
546:1402.0054
499:CiteSeerX
284:×
738:ICM 2018
634:MIT News
613:19282287
521:14350287
362:2.371552
269:Research
228:Bulgaria
155:Stanford
654:at the
573:2267837
72:Caltech
611:
601:
571:
561:
519:
501:
495:(STOC)
339:, the
122:Fields
41:, 2012
609:S2CID
569:S2CID
541:arXiv
517:S2CID
437:(PDF)
318:2.373
232:Sofia
807:DBLP
599:ISBN
559:ISBN
257:and
198:and
805:at
591:doi
551:doi
509:doi
150:MIT
819::
736:,
712:,
689:,
671:,
632:,
620:^
607:,
597:,
567:,
557:,
549:,
515:,
507:,
481:^
450:^
419:^
407:.
379:.
250:.
218:.
593::
553::
543::
511::
367:)
358:n
354:(
351:O
323:)
314:n
310:(
307:O
287:n
281:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.