Each semester, Associate Professor Virginia Vassilevska Williams tries to impart one fundamental lesson to her computer-science undergraduates: Math is the foundation of everything.
Often, students come into Williams’ class, 6.006 (Introduction to Algorithms), wanting to dive into advanced programming that power the latest, greatest computing techniques. Her lessons instead focus on how algorithms are designed around core mathematical models and concepts.
“When taking an algorithms class, many students expect to program a lot and perhaps use deep learning, but it’s very mathematical and has very little programming,” says Williams, who recently earned tenure in the Department of Electrical Engineering and Computer Science. “We don’t have much time together in class (only two hours a week), but I hope in that time they get to see a little of the beauty of math — because math allows you to see how and why everything works together. It really is a beautiful thing.”
Williams’ life is very much shaped by math. As a child of two mathematician parents, she fell in love with the subject early on. But even though she excelled in the subject, her high school classes focused on German, writing, and biology. Returning to her first love in college and beyond, she applied her math skills to make waves in computer science.
In highly influential work, Williams in 2012 improved an algorithm for “matrix multiplication” — a fundamental operation across computer science — that was thought to be the fastest iteration for 24 years. Years later, she co-founded an emerging field called “fine-grained complexity,” which seeks to explain, in part, how fast certain algorithms can solve various problems.
In matrix multiplication, her work has now shifted slightly to showing that existing techniques “cannot do better,” she says. “We couldn’t improve the performance of our own algorithms anymore, so we came up with ways to explain why we couldn’t and why other methods can’t improve the performance either.”
Winding path to math
Growing up in Sofia, Bulgaria, Williams loved math and was a gifted student. But her parents often reminded her the mathematician’s life wasn’t exactly glamorous —especially when trying to find faculty gigs in the same area for two people. They sometimes traveled where work took them.
That included a brief odyssey around the U.S. as a child. The first stop was Laramie, Wyoming. Her parents were visiting professors at the University of Wyoming, while Williams initially struggled through fourth grade because of the language barrier. “I didn’t really speak English, and was thrown into this school. My brother and I learned English watching the Disney channel, which was pretty fun,” says Williams, who today speaks Bulgarian, English, German, and some Russian.
The next stop was Los Angeles — right around the time of the Rodney King riots. “The house on the other side of our street was set on fire,” Williams recalls. “Those were some very strange memories of L.A.”
Returning to Bulgaria after two years, Williams decided to “explore her options” outside math by enrolling in the German Language High School in Sofia, the country’s top high school at the time, where she studied the German language, literature, history, and other humanities subjects. But, when it came to applying to colleges, she could never shake her first love. “I really tried to like the humanities, and what I learned is very helpful to me nowadays. But those subjects were very hard for me. My brain just doesn’t work that way,” she says. “I went back to what I like.”
Transfixed by algorithms
In 1999, Williams enrolled in Caltech. In her sophomore year, she became smitten by an exciting new field: computer science. “I took my first programming course, and I loved it,” she says.
She became transfixed by matrix multiplication algorithms, which have some heavy-duty math at their core. These algorithms compute multiple arrays of numbers corresponding to some data and output a single combined matrix of some target values. Applications are wide-ranging, including computer graphics, product design, artificial intelligence, and biotechnology.
As a PhD student at Carnegie Mellon, and beyond, she published numerous papers, on topics such as developing fast matrix multiplication algorithms in special algebraic structures, with applications including flight scheduling and network routing. After earning her PhD, she took on a series of postdoc and researcher positions at the Institute for Advanced Study, the University of California at Berkeley, and Stanford University, where she landed a faculty position in 2013 teaching courses on algorithms.
In 2012, she developed a new algorithm that was faster than the Coppersmith–Winograd algorithm, which had reigned supreme in matrix multiplication since the 1980s. Williams’ method reduced the number of steps required to multiply matrices. Her algorithm is only slightly slower than the current record-holder.
Dealing with complexity
Between 2010 and 2015, Williams and her husband, Ryan Williams, who is also an MIT professor, became main founders of “fine-grained complexity.” The older field of “computational complexity” finds provably efficient algorithms and algorithms that are probably inefficient, based on some threshold of computational steps they take to solve a problem.
Fine-grained complexity groups problems together by computational equivalence to better prove if algorithms are truly optimal or not. For instance, two problems may appear very different in what they solve and how many steps algorithms take to solve them. But fine-grained complexity shows such problems are secretly the same. Therefore, if an algorithm exists for one problem that uses fewer steps, then there must exist an algorithm for the other problem that uses fewer steps, and vice versa. On the flip side, if there exists a provably optimal algorithm for one problem, then all equivalent problems must have optimal algorithms. If someone ever finds a much faster algorithm for one problem, all the equivalent problems can be solved faster.
Since co-launching the field, “it’s ballooned,” Williams says. “For most theoretical computer science conferences, you can now submit your paper under the heading ‘fine-grained complexity.’”
In 2017, Williams came to MIT, where she says she has found impassioned, likeminded researchers. Many graduate students and colleagues, for instance, are working in topics related to fine-grained complexity. In turn, her students have introduced her to other subjects, such as cryptography, where she’s now introducing ideas from fine-grained complexity.
She also sometimes studies “computational social choice,” a field that caught her eye during graduate school. Her work focuses on examining the computational complexity needed to rig sports games, voting schemes, and other systems where competitors are placed in paired brackets. If someone knows, for instance, which player will win in paired match-ups, a tournament organizer can place all players in specific positions in the initial seeding to ensure a certain player wins it all.
Simulating all the possible combinations to rig these schemes can be very computationally complex. But Williams, an avid tennis player, authored a 2010 paper that found it’s fairly simple to rig a single-elimination tournament so a certain player wins, depending on accurate predictions for match-up winners and other factors.
This year she co-wrote a paper that showed a tournament organizer could arrange an initial seeding and bribe certain top players — within a specific budget — to ensure a favorite player wins the tournament. “When I need a break from my usual work, I work in this field,” Williams says. “It’s a fun change of pace.”
Thanks to the ubiquity of computing today, Williams’ graduate students often enter her classroom far more experienced in computer science than she was at their age. But to help steer them down a distinct path, she draws inspiration from her own college experiences, getting hooked on specific topics she still pursues today.
“In order to do good research, you have to obsess over a problem,” Williams says. “I want them to find something in my course they can obsess over.”
Ai
via https://www.AiUpNow.com
January 7, 2020 at 12:04AM by Rob Matheson | MIT News Office, Khareem Sudlow
