A 30-year-old conjecture about the structure of building blocks of computer circuits which puzzled several computer scientists over many years has been solved by a researcher. Known as the “Sensitivity” Conjecture, it was one of the most frustrating open problems in the area of theoretical computer science. Several prominent scientists in discrete maths and theoretical computer science tried to solve it.
The conjecture involves Boolean functions, rules for converting input bits to 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. The computer circuits are a combination of Boolean functions and is the brick and mortar of everything in computer science.
Researchers have tried to measure the complexity of a Boolean function over the years. Each measure tries to capture an aspect of how the input information determines the output. “Sensitivity” measures the chances of how the change in a single input bit affects the output. Similarly, the query complexity calculates the number of input bits needed to be sure of the output. Scientists have found that the measures fit into one framework, hence the value of one of them is a rough estimate of the value of others. However, only the complexity did not fit in: sensitivity.
Noam Nisan, Hebrew University and Mario Szegedy, Rutgers University conjectured in 1992 that the sensitivity indeed fits in the framework although no one could prove it. Scientists wrote long papers in the hope of the slightest progress. But now, Hao Huang, a mathematician at Emory University has proved it with a simple two-page argument about the combinatorics of points on cubes. Scientists have called the proof a “book” proof in connection to the notion of Paul Erdos that a celestial book is maintained where the proof of every theorem is maintained.
In a Boolean function, the output is decided by a series of input bits similar to a bank loan application where there are several questions, whose answers on processing determine if the applicant is eligible for the loan. On denial of application one may think if a single question would change the outcome. If one lie flips the outcome then the function is sensitive to the particular bit. If seven lies would have individually flipped the outcome then the sensitivity of the Boolean function is seven. Overall sensitivity is calculated as the largest sensitivity value when considering all possible loan profiles.
Sensitivity is an easy complexity to compute but it is not the only illuminating measure. Instead of paper application, the applicant could be interviewed where answer of one question determines the next. The maximum possible questions needed to ask is the query complexity of the function. There are several real world applications of this measure such as classification algorithm in machine learning, diagnosis of diseases. A low query complexity often makes things simpler. There are several other measures, such as the simplest way to write a function as a mathematical expression, a quantum physics version of query complexity.
With the exception of sensitivity, scientists proved that all the measures are very closely linked. They have a polynomial relationship to one another, like one measure may be nearly the square root or cube of another. Only sensitivity did not fit in. Scientists thought it belonged but could not prove it for nearly 30 years.
Huang heard the sensitivity conjecture in 2012 over lunch with Micahel Saks, a mathematician at Institute for Advanced Study where Huang was a postdoctoral fellow. He was obsessed with the simplicity and elegance of the conjecture. He added it to a list of his “secret problems” and tried to solve it whenever he published a paper or learned a new tool. He knew that the conjecture could be proven if another conjecture about collections of points on cubes was proven. There is an easy way to go from string of n 0’s and 1’s to a point on cube with n dimensions. The n bits are used as coordinates of the point. 00,01,10 and 11 correspond to four corners of square in two dimensions: (0,0), (0,1), (1,0) and (1,1). A boolean function can be considered as a rule for coloring the corners with two different colors such as red for 0 and blue for 1.
Craig Gotsman and Nati Linial figured out in 1992 that the proof of the sensitivity conjecture could be reduced to a simple question regarding cubes of different dimensions. If a collection of more than half of cube corners are chosen and coloured red is there a redpoint always which is connected to other red points. Four points (0,0,0),(1,1,0), (1,0,1) and (0,1,1) sit across the diagonals. However, when more than half points are coloured red, a connection is established and the question is how are the connections distributed.
Huang tried to understand the question using matrix which tracks the points that are connected and then examine the eigenvalues. He tried on the idea for five years with no success.
Then in 2018, he used Cauchy interlace theorem, a 200-year-old theorem relating the eigenvalues of the matrix to a submatrix making it the optimal tool to understand the relationship between the cube and subset of corners. He requested a grant from the National Science Foundation to explore the idea.
But last month he realised that by switching the signs of few numbers in matrix he could prove that in any collection of more than half the number of points, there is some point which is connected to a minimum of square root of n other points.
The proof is simple enough to understand in one sitting and it might be taught now in every combinatorics course at master level. The proof is strong enough to prove the conjecture and it can give new insights about measures of complexity.
Journal Reference: arxiv