With the advent of social media networks like Facebook and Snapchat, our world is increasingly connected and complicated. Understanding the nature of these networks now requires wading through enormous amounts of information and performing overwhelming computations. This problem will only multiply in the future, making arriving at any meaningful conclusions about data unimaginably difficult.
This was the dilemma that Daniel Spielman (YC ’92), Sterling Professor of Computer Science and Professor of Statistics and Data Science and Mathematics at Yale, sought to solve. He wanted to use a technique called sparsification, which takes large data sets and removes points that do not contribute important information about the data. He found inspiration in an almost unrelated field of mathematics. This venture helped him solve a decades-old problem in the field of operator theory, earning him the Ciprian Foias prize and the Polya Prize.
Spielman had initially thought that his problem was in the realm of linear algebra. “It’s one of those courses every math major takes that talks about finite-dimensional spaces,” Spielman said. However, upon discussion with visiting professors and his graduate students, Adam Marcus, a postdoc at Princeton University, and Nikhil Srivastava, a graduate student at UC Berkeley, he realized that his sparsification problem mirrored an existing problem in operator theory called the Kadison-Singer problem, developed in 1959. The Kadison-Singer problem, which examines how to divide a group into two groups that are as equal as possible, had previously been discussed in the fields of quantum physics and computer science but had not been explored in the field of data science.
The Kadison-Singer problem, or the concept of partitioning groups in general, is relevant in everyday decision-making. Suppose a PE teacher needs to divide a class of students into two equally skilled teams to play kickball. To achieve this, he will need to rank the students by their kicking, throwing, and catching abilities and separate students so that the two teams are approximately equal in all three abilities. Spielman’s initial paper proved that the Kadison-Singer problem was an equivalent restatement of the sparsification problem. In a monumental 2014 paper, Spielman and his colleagues proved the existence of a solution, countering Kadison and Singer’s decades-long conjecture that not every mathematical group could be divided equally. Marcus, Srivastava, and Spielman’s work earned them the Polya Prize in 2014. Proving the ability to partition groups provided the impetus to explore new ways to divide networks into relatively equal groups, which aided in network sparsification: if one group was simply omitted from the network, there wasn’t any net loss of information. In subsequent years, Spielman and his team worked on developing mathematical tools to achieve such data sparsification, for which they received the Ciprian Foias prize in Operator Theory earlier this year.
Spielman’s transformation of a linear algebra problem into an operator theory problem reflects his general approach to mathematics. He first became interested in solving challenging puzzles in the fourth grade, took college math and programming classes in high school, and pursued a bachelor’s degree in mathematics and computer science at Yale. He has always been interested in using computational tools to solve problems. “There’s a marriage between [math and computer science]. I was once trying a proof in my undergraduate lab, and a computer program found a counterexample in a couple of months that I wouldn’t have found in a hundred years,” Spielman said.
Spielman now employs computation in all of the problems he chooses to solve. “I keep a list of problems that interest me, and when I am interested in working on a problem, I check if there’s a similar problem on my list and if someone’s already worked on similar problems,” Spielman said. He claims he cannot predict what problem he wants to solve next. He may continue working on sparsification, networks, or topics in linear algebra but will inevitably draw inspiration from other mathematical concepts and fields. “I completely change my research agenda every few years,” Spielman said.
He is currently working on establishing the Kline Tower Institute (KTI) for the Foundations of Data Science to sponsor talks between experts in different fields who want to employ data science techniques in their work. Ultimately, Spielman encourages every college student to try some math classes. “You never know what’s going to be useful, so you should take classes that interest you. Later in life, you may find that useful connection,” Spielman said.