In 1637, the French mathematician Pierre de Fermat scribbled in a book that he had a proof for a theorem, which the margin was too small to contain. It seems likely that he was mistaken about his famous “last theorem,” since no such proof was found for 358 years, and even then it required more than 100 pages and used mathematics that didn’t exist in his time.
By contrast, the Boolean “sensitivity conjecture” is relatively recent, but after nearly 30 years and repeated failures it seemed likely that any proof would also be a long and difficult slog. In July, 2019, however, mathematician Hao Huang of Emory University in Atlanta posted a short paper that completed its proof in a couple of pages in a way that experts found very convincing. Indeed, they immediately described it as “from the book,” a tome imagined by the great 20th-century mathematician Paul Erdös in which God records the shortest and most illuminating proof of each theorem.
The new proof closes a nagging loophole by confirming that “sensitivity” of any Boolean function is closely related to other measures of its computational complexity. “In the past, computer scientists studied a lot of different complexity measures. All but one of them were known to be polynomially related,” Huang said, meaning that their possible values are constrained by powers of the others. “My work is basically to put the sensitivity—the last exception—into this category.”
Figure. Emory University mathematician Hao Huang, who developed the proof of the sensitivity conjecture.
Algorithmic complexity theory aims to provide strict upper and lower bounds on the difficulty of calculations, especially as the problems get larger. Its best-known open question, P≠NP, concerns the existence of problems whose solution can be verified with computational resources that grow as a polynomial function of the problem size but which require much more effort to solve in the first place. The new result is “not going to spring open P≠NP,” cautioned Kenneth Regan of the University at Buffalo (part of the State University of New York system). Nonetheless, he noted that the sensitivity conjecture is closely related to “the tools that people have been using to try to get a handle on P≠NP.”
Measures of Complexity
Boolean functions are at the heart of digital computation, producing a one-bit (zero or one) output, based on the values of a string of input bits. Sensitivity is one measure of a Boolean function’s complexity: Considering all possible input strings, the sensitivity is the largest number of input bits whose individual flipping (from zero to one or vice versa) changes the output.
Sometimes flipping any input bit is enough. For example, the parity function, which reports whether the input has an even or odd number of ones, changes value for any input bit, for any input string. Thus its sensitivity has the maximum possible value, equal to the number of input bits. The logical “and” of all the bits also has maximum sensitivity, because, for an all-ones input, then changing any bit to zero flips the output.
Other functions are less sensitive, so that for all input strings there are some bits that cannot on their own change the answer. For example, the OR-of-AND function asks, for a bunch of non-overlapping blocks of input bits, whether any of them has all ones for inputs. Changing the answer from yes can only be done by flipping a bit in a unique all-ones block, while changing the answer from no can only be done by flipping the last remaining bit that is not zero in one of the blocks. The sensitivity is the larger of the number of bits per block or the number of blocks.
Computer scientists have explored several other measures of computational complexity. The “block sensitivity,” for example, quantifies how many blocks containing multiple input bits change the output when they are simultaneously flipped. Another measure is the function’s “degree,” which is the highest total exponent in the polynomial that reproduces the output when the inputs are zero or one.
Other measures include decision-tree depth (the minimum number of yes-or-no questions needed to guarantee knowing the output), as well as its quantum and random variants, and certificate complexity (the number of input bits needed to guarantee knowing the output). Researchers proved long ago that all these other complexity measures are closely related. Specifically, upper or lower bounds on their values, for any Boolean function, can be expressed as polynomials of the others, which is useful for proofs. “If they are polynomially related, they are roughly of the same order of magnitude,” Huang said, “so instead of looking at the more difficult ones, you can look at a simpler one.”
Coloring Hypercubes
Some important conclusions have been mathematically expressed only in terms of sensitivity, however, and until now there had been no proof that they were also members of this club, although it was widely thought to be. Indeed, in 1992, Noam Nisan of the Hebrew University of Jerusalem and Mario Szegedy, then at AT&T Bell Laboratories, explicitly conjectured that the block sensitivity of a function could not exceed some fixed power of its sensitivity.
A critical strategy for proving this “sensitivity conjecture” was provided the same year by Craig Gotsman and Nathan Linial, both then at the Hebrew University of Jerusalem, who connected the sensitivity with the graph-theoretical properties of corners of a hypercube.
The coordinates of any corner of an n-dimensional hypercube can be written as an n-bit string of zeroes and ones. A Boolean function then corresponds to coloring the corners, say red when the function is one and white when it is zero.
If exactly half of the corners are red (and half white), they can be arranged so that no corner has a like-colored neighbor, for example by coloring them according the parity function of their coordinates. If even one additional corner is colored red, however, it turns out that at least one of the red corners must have many red neighbors. The question is how many? The largest number, among all red corners, is called the degree of the framework (which is not the same as the degree of the function).
The proof “provides a useful addition to the toolbox of mathematics and computer science that hopefully will see more application in the future.”
In this picture, the sensitivity of a function is the maximum number of white corners (opposite output) sharing an edge (one input-bit flip) with any red point. The remainder of the n edges are connected to red points, so the sensitivity is closely connected to the subgraph’s degree.
The half-page proof by Gotsman and Linial showed roughly that a bound on a subgraph’s degree, as a function of n, is equivalent to a bound on the sensitivity of a Boolean function, as a function of the degree of its polynomial. Thus, a theorem about one becomes a theorem about the other, opening the door to a proof of the sensitivity conjecture.
Changing Signs
In spite of this clear roadmap, and decades of attempts, this promise was only realized with Huang’s proof. What Huang showed was that if even one more than half of the hypercube’s corners are red, at least one of them will have at least √n red neighbors, precisely what Gotsman and Linial suspected. This implies that the degree of the function is no greater than the square of its sensitivity. Together with a previous theorem that the block sensitivity is no greater than the square of the degree, this means that the block sensitivity does not exceed the fourth power of the sensitivity. This confirms the conjecture and thus connects sensitivity to all the other complexity measures.
The proof is based on something called the adjacency matrix, whose 2n rows and 2n columns correspond to the corners of the hypercube, and whose elements are zero unless the corners are same-colored neighbors. The critical trick is that the non-zero elements for neighbors are usually assigned a value of +1, but Huang assigned some of them a value of -1. Carefully choosing the negative values allowed him to use known matrix theorems to show that at least one row of the matrix must have at least √n entries.
Aaronson wrote on his blog, “How could such an elementary 1.5-page argument have been overlooked for 30 years? I don’t have a compelling answer to that, besides noting that ‘short’ and ‘elementary’ often have little to do with ‘obvious.’ Once you start looking at … this matrix …, the pieces snap together in precisely the right way—but how would you know to look at that?”
“For making a calculation it’s straightforward to go through every step,” Huang noted. In contrast, “a proof is easy to verify, but it’s difficult to come up with a new proof.”
Since encountering this problem in 2012, Huang wrote in a comment on Scott Aaronson’s blog, “I revisited this conjecture every time I learned a new tool—without any success, though.”
More recently, he added, “I had been looking at other kinds of problems at the same time, and I used this adjacency matrix a lot,” he said. “I realized that it can be also applied to this particular sensitivity conjecture, and that’s how I came out with the proof.”
Regan, who had previously explored similar ideas, said the cancellations allowed by making some matrix elements negative is critical, and are reminiscent of the interference that quantum algorithms exploited.
Huang said the proof “provides a useful addition to the toolbox of mathematics and computer science that hopefully will see more application in the future,” although he noted that in math this process often takes many years. He also hoped that the work would be an inspiration for graduate students to attack long-standing unsolved problems.
Huang, H.,
Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, July 1, 2019 https://arxiv.org/abs/1907.00847
Klarreich, E.,
Decades-Old Computer Science Conjecture Solved in Two Pages, Quanta, July 25, 2019, http://bit.ly/36ipHTo
Gotsman, C., and Linial, N.,
The equivalence of two problems on the cube, Journal of Combinatorial Theory, Series 1, Volume 61 Issue 1, September 1992, pp. 142—146.
Sensitivity Conjecture Resolved, Scott Aaronson at Shtetl-Optimized, July 2, 2019.
Tools and Sensitivity, Ken Regan at Gödel’s Lost Letter and P=NP, July 12, 2019.
Amazing: Hao Huang Proved the Sensitivity Conjecture! Gil Kalai at Combinatorics and More, July 2, 2019
Join the Discussion (0)
Become a Member or Sign In to Post a Comment