เวอร์จิเนีย วาสซิลเลฟสกา วิลเลียมส์ ผู้บุกเบิกทฤษฎีความซับซ้อนและอัลกอริทึม

เวอร์จิเนีย วาสซิลเลฟสกา วิลเลียมส์ (Virginia Vassilevska Williams) เป็นนักวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีและนักคณิตศาสตร์ที่มีชื่อเสียงระดับโลก โดยมีความเชี่ยวชาญเป็นพิเศษในด้านทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) และการออกแบบอัลกอริทึม ปัจจุบันเธอเป็นศาสตราจารย์ร่วม (Associate Professor) ในตำแหน่ง Steven and Renee Finn Career Development ในภาควิชาวิศวกรรมไฟฟ้าและวิทยาการคอมพิวเตอร์ที่สถาบันเทคโนโลยีแมสซาชูเซตส์ (MIT)

ความเชี่ยวชาญและผลงานทางวิชาการ

วิลเลียมส์เป็นที่รู้จักจากการสร้างความก้าวหน้าครั้งสำคัญในหลายด้านของวิทยาการคอมพิวเตอร์เชิงทฤษฎี ดังนี้:

• การคูณเมทริกซ์แบบรวดเร็ว (Fast Matrix Multiplication): เธอประสบความสำเร็จในการพัฒนาอัลกอริทึมที่ลดเวลาในการคำนวณการคูณเมทริกซ์ขนาด n × n ซึ่งเป็นรากฐานสำคัญของงานคำนวณจำนวนมากในปัจจุบัน
• อัลกอริทึมแบบไดนามิก (Dynamic Algorithms): การวิจัยของเธอครอบคลุมถึงการพัฒนาอัลกอริทึมที่สามารถปรับปรุงข้อมูลได้อย่างมีประสิทธิภาพเมื่อมีการเปลี่ยนแปลงข้อมูลนำเข้า
• ทฤษฎีความซับซ้อนแบบละเอียด (Fine-grained Complexity): เธอมีบทบาทสำคัญในการร่วมพัฒนาสาขาวิชานี้ ซึ่งมุ่งเน้นการวิเคราะห์ขีดจำกัดล่างของเวลาในการประมวลผลสำหรับปัญหาที่เชื่อว่าไม่สามารถแก้ไขได้ในเวลาพหุนามที่รวดเร็วขึ้น

ประวัติการศึกษาและเส้นทางอาชีพ

วิลเลียมส์เกิดที่ประเทศบัลแกเรีย และสำเร็จการศึกษาระดับมัธยมปลายจากโรงเรียนสอนภาษาเยอรมันในกรุงโซเฟีย จากนั้นเธอได้ย้ายมาศึกษาต่อในสหรัฐอเมริกา โดยสำเร็จการศึกษาระดับปริญญาตรีจากสถาบันเทคโนโลยีแคลิฟอร์เนีย (Caltech) ในปี 2003 และระดับปริญญาเอก (Ph.D.) จากมหาวิทยาลัยคาร์เนกีเมลลอน (Carnegie Mellon University) ในปี 2008 โดยวิทยานิพนธ์ของเธอเรื่อง Efficient Algorithms for Path Problems in Weighted Graphs อยู่ภายใต้การดูแลของ Guy Blelloch

หลังจากผ่านการทำวิจัยหลังปริญญาเอกที่สถาบันเพื่อการศึกษาขั้นสูง (Institute for Advanced Study) และมหาวิทยาลัยแคลิฟอร์เนีย เบิร์กลีย์ (UC Berkeley) เธอได้เริ่มต้นอาชีพอาจารย์ที่มหาวิทยาลัยสแตนฟอร์ด (Stanford University) ในปี 2013 ก่อนจะย้ายมาดำรงตำแหน่งศาสตราจารย์ร่วมที่ MIT ในปี 2017

ความก้าวหน้าในการคูณเมทริกซ์

ในปี 2011 วิลเลียมส์ได้ค้นพบอัลกอริทึมสำหรับการคูณเมทริกซ์ขนาด n × n ที่ใช้เวลาในระดับ O(n^2.373) ซึ่งเป็นการทำลายสถิติของอัลกอริทึม Coppersmith–Winograd ที่ครองตำแหน่งอัลกอริทึมที่เร็วที่สุดมานานถึง 24 ปี

ผลงานนี้เกิดขึ้นจากการพัฒนาแนวคิดอย่างเป็นอิสระ ซึ่งต่อมาเธอได้นำแนวคิดของ Andrew Stothers มาผสมผสานเพื่อปรับปรุงขอบเขตเวลาให้ดียิ่งขึ้น และในเวลาต่อมา (ปี 2023 และ 2024) เธอและคณะผู้ร่วมวิจัยได้ขยายขอบเขตนี้ให้ลดลงเหลือ O(n^2.371552) และ O(n^2.371339) ตามลำดับ

รางวัลและการยอมรับ

วิลเลียมส์ได้รับทุน NSF Computing Innovation Fellow ระหว่างปี 2009–2011 และได้รับทุน Sloan Research Fellowship ในปี 2017 นอกจากนี้ เธอได้รับเกียรติให้เป็นวิทยากรในงานประชุมคณิตศาสตร์นานาชาติ (International Congress of Mathematicians) ปี 2018 ในหัวข้อด้านคณิตศาสตร์ของวิทยาการคอมพิวเตอร์

ชีวิตส่วนตัว

เธอเป็นบุตรสาวของ Panayot Vassilevski และ Tanya Kostova-Vassilevska ซึ่งทั้งคู่เป็นนักคณิตศาสตร์ประยุกต์ เธอสมรสกับ Ryan Williams ซึ่งเป็นศาสตราจารย์ด้านวิทยาการคอมพิวเตอร์ที่ MIT เช่นกัน โดยทั้งคู่ได้ร่วมงานกันในด้านทฤษฎีความซับซ้อนแบบละเอียด