Decades-Old Computer Science Conjecture Solved in Two Pages

A paper posted online this month has settled a nearly 30-year-old conjecture about the structure of the fundamental building blocks of computer circuits. This “sensitivity” conjecture has stumped many of the most prominent computer scientists over the years, yet the new proof is so simple that one researcher summed it up in a single tweet.

“This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science,” wrote Scott Aaronson of the University of Texas, Austin, in a blog post. “The list of people who tried to solve it and failed is like a who’s who of discrete math and theoretical computer science,” he added in an email.

The conjecture concerns Boolean functions, rules for transforming a string of input bits (0s and 1s) into a single output bit. One such rule is to output a 1 provided any of the input bits is 1, and a 0 otherwise; another rule is to output a 0 if the string has an even number of 1s, and a 1 otherwise. Every computer circuit is some combination of Boolean functions, making them “the bricks and mortar of whatever you’re doing in computer science,” said Rocco Servedio of Columbia University.

Over the years, computer scientists have developed many ways to measure the complexity of a given Boolean function. Each measure captures a different aspect of how the information in the input string determines the output bit. For instance, the “sensitivity” of a Boolean function tracks, roughly speaking, the likelihood that flipping a single input bit will alter the output bit. And “query complexity” calculates how many input bits you have to ask about before you can be sure of the output.

Each measure provides a unique window into the structure of the Boolean function. Yet computer scientists have found that nearly all these measures fit into a unified framework, so that the value of any one of them is a rough gauge for the value of the others. Only one complexity measure didn’t seem to fit in: sensitivity.

In 1992, Noam Nisan of the Hebrew University of Jerusalem and Mario Szegedy, now of Rutgers University, conjectured that sensitivity does indeed fit into this framework. But no one could prove it. “This, I would say, probably was the outstanding open question in the study of Boolean functions,” Servedio said.

“People wrote long, complicated papers trying to make the tiniest progress,” said Ryan O’Donnell of Carnegie Mellon University.

Now Hao Huang, a mathematician at Emory University, has proved the sensitivity conjecture with an ingenious but elementary two-page argument about the combinatorics of points on cubes. “It is just beautiful, like a precious pearl,” wrote Claire Mathieu, of the French National Center for Scientific Research, during a Skype interview.

Aaronson and O’Donnell both called Huang’s paper the “book” proof of the sensitivity conjecture, referring to Paul Erdős’ notion of a celestial book in which God writes the perfect proof of every theorem. “I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this,” Aaronson wrote.

A Sensitive Matter

Imagine, Mathieu said, that you are filling out a series of yes/no questions on a bank loan application. When you’re done, the banker will score your results and tell you whether you qualify for a loan. This process is a Boolean function: Your answers are the input bits, and the banker’s decision is the output bit.

If your application gets denied, you might wonder whether you could have changed the outcome by lying on a single question — perhaps, by claiming that you earn more than $50,000 when you really don’t. If that lie would have flipped the outcome, computer scientists say that the Boolean function is “sensitive” to the value of that particular bit. If, say, there are seven different lies you could have told that would have each separately flipped the outcome, then for your loan profile, the sensitivity of the Boolean function is seven.

Computer scientists define the overall sensitivity of the Boolean function as the biggest sensitivity value when looking at all the different possible loan profiles. In some sense, this measure calculates how many of the questions are truly important in the most borderline cases — the applications that could most easily have swung the other way if they’d been ever so slightly different.

Sensitivity is usually one of the easiest complexity measures to compute, but it’s far from the only illuminating measure. For instance, instead of handing you a paper application, the banker could have interviewed you, starting with a single question and then using your answer to determine what question to ask next. The largest number of questions the banker would ever need to ask before reaching a decision is the Boolean function’s query complexity.

This measure arises in a host of settings — for instance, a doctor might want to send a patient for as few tests as possible before reaching a diagnosis, or a machine learning expert might want an algorithm to examine as few features of an object as possible before classifying it. “In a lot of situations — diagnostic situations or learning situations — you’re really happy if the underlying rule … has low query complexity,” O’Donnell said.

Other measures involve looking for the simplest way to write the Boolean function as a mathematical expression, or calculating how many answers the banker would have to show a boss to prove they had made the right loan decision. There’s even a quantum physics version of query complexity in which the banker can ask a “superposition” of several questions at the same time. Figuring out how this measure relates to other complexity measures has helped researchers understand the limitations of quantum algorithms.

With the single exception of sensitivity, computer scientists proved that all these measures are closely linked. Specifically, they have a polynomial relationship to each other — for example, one measure might be roughly the square or cube or square root of another. Only sensitivity stubbornly refused to fit into this neat characterization. Many researchers suspected that it did indeed belong, but they couldn’t prove that there were no strange Boolean functions out there whose sensitivity had an exponential rather than polynomial relationship to the other measures, which in this setting would mean that the sensitivity measure is vastly smaller than the other measures.

“This question was a thorn in people’s sides for 30 years,” Aaronson said.

Cornering the Solution

Huang heard about the sensitivity conjecture in late 2012, over lunch with the mathematician Michael Saks at the Institute for Advanced Study, where Huang was a postdoctoral fellow. He was immediately taken with the conjecture’s simplicity and elegance. “Starting from that moment, I became really obsessed with thinking about it,” he said.

Huang added the sensitivity conjecture to a “secret list” of problems he was interested in, and whenever he learned about a new mathematical tool, he considered whether it might help. “Every time after I’d publish a new paper, I would always go back to this problem,” he said. “Of course, I would give up after a certain amount of time and work on some more realistic problem.”

Huang knew, as did the broader research community, that the sensitivity conjecture could be settled if mathematicians could prove an easily stated conjecture about collections of points on cubes of different dimensions. There’s a natural way to go from a string of n 0s and 1s to a point on an n-dimensional cube: Simply use the n bits as the coordinates of the point.

For instance, the four two-bit strings — 00, 01, 10 and 11 — correspond to the four corners of a square in the two-dimensional plane: (0,0), (0,1), (1,0) and (1,1).  Likewise, the eight three-bit strings correspond to the eight corners of a three-dimensional cube, and so on in higher dimensions. A Boolean function, in turn, can be thought of as a rule for coloring these corners with two different colors (say, red for 0 and blue for 1).

In 1992, Craig Gotsman, now of the New Jersey Institute of Technology, and Nati Linial of Hebrew University figured out that proving the sensitivity conjecture can be reduced to answering a simple question about cubes of different dimensions: If you choose any collection of more than half the corners of a cube and color them red, is there always some red point that is connected to many other red points? (Here, by “connected,” we mean that the two points share one of the outer edges of the cube, as opposed to being across a diagonal.)

If your collection contains exactly half the corners of the cube, it’s possible that none of them will be connected. For example, among the eight corners of the three-dimensional cube, the four points (0,0,0), (1,1,0), (1,0,1) and (0,1,1) all sit across diagonals from one another. But as soon as more than half the points in a cube of any dimension are colored red, some connections between red points must pop up. The question is: How are these connections distributed? Will there be at least one highly connected point?

In 2013, Huang started thinking that the best route to understanding this question might be through the standard method of representing a network with a matrix that tracks which points are connected and then examining a set of numbers called the matrix’s eigenvalues. For five years he kept revisiting this idea, without success. “But at least thinking about it [helped] me quickly fall asleep many nights,” he commented on Aaronson’s blog post.

Then in 2018, it occurred to Huang to use a 200-year-old piece of mathematics called the Cauchy interlace theorem, which relates a matrix’s eigenvalues to those of a submatrix, making it potentially the perfect tool to study the relationship between a cube and a subset of its corners. Huang decided to request a grant from the National Science Foundation to explore this idea further.

Then last month, as he sat in a Madrid hotel writing his grant proposal, he suddenly realized that he could push this approach all the way to fruition simply by switching the signs of some of the numbers in his matrix. In this way, he was able to prove that in any collection of more than half the points in an n-dimensional cube, there will be some point that is connected to at least $latex \sqrt{n}$ of the other points — and the sensitivity conjecture instantly followed from this result.

When Huang’s paper landed in Mathieu’s inbox, her first reaction was “uh-oh,” she said. “When a problem has been around 30 years and everybody has heard about it, probably the proof is either very long and tedious and complicated, or it’s very deep.” She opened the paper expecting to understand nothing.

But the proof was simple enough for Mathieu and many other researchers to digest in one sitting. “I expect that this fall it will be taught — in a single lecture — in every master’s-level combinatorics course,” she messaged over Skype.

Huang’s result is even stronger than necessary to prove the sensitivity conjecture, and this power should yield new insights about complexity measures. “It adds to our toolkit for maybe trying to answer other questions in the analysis of Boolean functions,” Servedio said.

Most importantly, though, Huang’s result lays to rest nagging worries about whether sensitivity might be some strange outlier in the world of complexity measures, Servedio said. “I think a lot of people slept easier that night, after hearing about this.”

This article was reprinted on Wired.com.