Infinite complexity

Bob Handelman

A visiting professor told mathematician Daniel Spielman ’92 one day about an unsolvable problem. Spielman thought he’d give it a shot. That was in 2008. Seven years later, he and his colleagues had learned a lot more than they’d expected. View full image

One day in 2008, a visiting professor dropped by the office of mathematician Daniel Spielman ’92 and asked, as he usually did during the alternating semesters he was teaching at Yale, what Spielman was working on.

Spielman told him. Gil Kalai, a mathematician himself then on leave from Hebrew University, said Spielman’s work reminded him of an old, enduring problem in theoretical physics. Kalai described it.

Spielman said he might be able to solve it.

You don’t understand, Kalai said. The question isn’t whether Daniel Spielman can solve the problem. The question isn’t even if anyone can solve the problem—because the consensus among theoretical physicists had long ago coalesced around an answer of No. The problem has no solution.

Spielman listened politely. He was no theoretical physicist; he freely acknowledged his ignorance of the subject. What he was, instead, was a mathematician, and he had a mathematician’s hunch.

This past spring the National Academy of Sciences rewarded Spielman and two collaborators with the 2021 Michael and Sheila Held Prize, one of the highest honors in computer science. Spielman’s hunch had paid off: one area of math can apply to disparate fields in ways you’d never anticipate.

“This happens a lot,” says Spielman, Sterling Professor of Computer Science and professor of statistics and data science. “There are all sorts of places where people have been burrowing really deeply into tunnels in one area of mathematics, and at some point they come along and they hit another area of mathematics, and you discover connections.”

The tunnel that Spielman was digging when he had his fateful discussion with Kalai involved “networks”—social networks, computer networks, communication networks. In graphing a social network, for instance, mathematicians will represent a single person as a dot, or a “node.” If they connect that node to another node, they draw a straight line, or an “edge.” Count the edges extending from any single node and you know its number of connections. Mathematicians, Spielman says, “call this ‘degree.’ Physicists call it ‘valence.’ Other people call it ‘How many friends do you have?’”

If the network you’re studying is a small town, the graph might be relatively simple. But what if you’re graphing a shipping service’s possible routes? Plot the collection points (front porches, outlet stores, drop boxes), then the airport hubs through which the packages pass, then the possible destinations (every street address and PO box in the United States and Canada). Then add up every conceivable path a single package might take. The answer might not be an infinity, and the time an algorithm needs to plot the most efficient path might not be an eternity. But if you want to send a birthday gift to Grandma that absolutely, positively has to be there overnight?

The possible solution that Spielman explored was “sparsificaton”—speeding up the algorithm by simplifying networks. “Which meant,” Spielman says, “dropping most connections”—or, in this metaphor, rerouting traffic onto only a few major roads.
As a practical matter, shipping companies wouldn’t survive without such shortcuts. Rather than figure out the most efficient path of each package in advance, they can leave the local logistics to regional dispatch centers, which might be operating according to algorithms of their own.

For Spielman, however, the challenge wasn’t to deliver the goods. It was more abstract: take a virtually infinitely complex system and see how far he could sparsify it without sacrificing its integrity. In 2008—around the time he was meeting with Kalai—he and his student Nikhil Srivastava ’10PhD (now at the University of California–Berkeley) were finishing “Graph Sparsification by Effective Resistances,” which appeared in Society for Industrial and Applied Mathematics Journal on Computing.

“We were able to show you can actually approximate any network,” Spielman says. “This was a sort of crazy result. It wasn’t necessarily practical”—it wouldn’t guarantee the most efficient route door to door, so to speak—“but it was mathematically very intriguing.”

Mathematically.
In using this word, Spielman is evoking the fundamental distinction in his field between math that is promising and math that is practical—between an algorithm that, after further burrowing, might eventually solve real-life problems or intersect with another tunnel, and an algorithm that’s ready to use today.

Another tunnel is what his intuition whispered to him while Kalai was describing the long-standing problem that theoretical physicists believed had no solution. The Kadison-Singer problem—formulated by mathematicians Richard Kadison and Isadore Singer in 1959—asks whether a mathematically complete description of a quantum subsystem might allow a mathematically complete description of the quantum system as a whole.

Spielman himself struggles to find a layperson’s explanation. The best he can do, he says, is: the Kadison-Singer problem “asks whether a large number of measurements made on a part of a quantum system uniquely determine the system as a whole.” (He also says, “If given a choice between attempting to explain the original KS problem and defending myself from a pride of hungry tigers, I’d give myself better odds with the tigers.”)

One reason that theoretical physicists thought the answer must be No is that the core principle of quantum mechanics is uncertainty—for instance, the impossibility of simultaneously measuring a particle’s position and velocity. You can’t use a subsystem of uncertainty to capture the system as a whole . . . can you?

Why not? thought Spielman. Wasn’t he doing the same thing, sort of? True, he wasn’t working in the quantum realm. But pruning a virtual infinity of choices in a system to describe a subsystem couldn’t be all that different from using a subsystem to describe a system.

His confidence only grew when Kalai referred Spielman to a paper he thought might help. It included a statement about vectors (or, in their terminology, degrees) and matrices (systems) that Spielman and his collaborators had already assumed was true. Tunnels were, indeed, converging.
“It looked like something we understood incredibly well,” Spielman says. Maybe he would never comprehend the implications for the quantum realm. “But at least this one version was something I could understand. So it was at least clear that the problem was fundamental in many different areas.”

The decision was easy. We’ll work on this, he thought. It’ll go pretty fast.

Five years passed.
Five not altogether unpleasant years: in 2008, Spielman and his collaborator Shang-Hua Teng won the Gödel Prize; in 2010 he received the Nevanlinna Prize; in 2012 he joined the inaugural class of Simons Investigators, a fellowship providing $660,000 in research funding over five years; in 2012, he received a MacArthur Fellowship. All these honors, though, recognized work that was receding farther and farther into the past, while the Kadison-Singer problem threatened to swallow his (and his colleagues’) future.

Vacations became distractions. Holidays became hurdles. If his wife told him she was going out for drinks with some nodes of hers, Spielman would think, Good. I’ll stay home and work on the Kadison-Singer problem, and I don’t have to worry about my wife having fun.

“It always felt like we were making progress,” he says. “We kept coming up with conjectures that were pretty and looked true.” Still, he couldn’t ignore the possibility that their tunnel was going in circles, at least regarding the Kadison-Singer problem.

“Maybe we should find a way out,” Spielman finally decided. He and his collaborators, Adam Marcus (now at the École polytechnique fédérale de Lausanne in Switzerland) and Srivastava, collated the hundreds of pages of emails they’d sent one another over the years and asked: Can we use them to do anything else that’s important?

Maybe, Spielman thought, they could use their math to find new applications for Ramanujan graphs—a sometime inspiration for Spielman’s past work, including his doctoral thesis at MIT. (He majored in mathematics and computer science at Yale.) He knew that Ramanujan graphs were extremely efficient. “If you want to be able to transmit messages through a network, these are the networks you would want,” Spielman says. “There’s no interference”—no bottlenecks where two messages block each other—“and there’s short paths between everything.” Srivastava soon located a paper that suggested a way to generate Ramanujan graphs. It was still missing a crucial step—but Spielman’s team realized they could derive that step from the techniques they’d been developing on their own for the Kadison-Singer problem.

“About a week later,” Spielman says, “we knew how to make Ramanujan graphs” using their own math. “It was a shockingly fast development. At which point I thought, ‘Okay, this is great. Even if we haven’t solved the Kadison-Singer problem, we’ve developed all this new mathematics, and we’ve used it do something, and maybe someone else will use it to solve the Kadison-Singer problem.”

Fortunately for Spielman and his two collaborators, nobody else did.
Instead, they did. “It was only by taking what we thought was a diversion,” Spielman says, “that a few months later we realized we actually had enough to solve the Kadison-Singer problem.”

To a layperson the word solve can be misleading. Spielman didn’t find the answer to the Kadison-Singer problem itself. Rather, he discovered that the answer to the question he had addressed in that long-ago office meeting with Kalai—the answer to the question of whether a solution to the Kadison-Singer problem was even possible—the answer that physicists had come to believe was No, was Yes.

Which is to say, mathematically, Spielman’s result is promising.

The citation for the Held Prize recognizes both achievements: generating new constructions of Ramanujan graphs and showing that the Kadison-Singer problem is potentially solvable. But the Held Prize citation also places their work within a specific context—one that a scientist harboring a mathematician’s hunch might especially appreciate: the collaboration “uncovered a deep new connection between linear algebra, geometry of polynomials, and graph theory that has inspired the next generation of theoretical computer scientists.”

Deeper tunnels. More degrees. New nodes.

Since the paper went online in 2013, mathematicians in multiple fields have been trying to wrest something practical from the promise inherent in the Kadison-Singer problem. Spielman and his collaborators have themselves written a paper, still undergoing peer review, that they think might advance that discussion.

In the meantime, the burrowing continues.