Breakthrough in sensitivity conjecture

Hao Huang's argument could finally help in the understanding of Boolean Functions

When you make an application for a mortgage, you have to answer many questions on a form. The lender will want details about your age, health, income, net worth, other debts, family situations, etc. Those answers can be translated into binary “yes” or “no” responses, so far as the lender is concerned. Ideally, the lender wants somebody who is under 45 (“yes” for positive), who is in good health, without family encumbrances, a working partner etc. 

The positive answers (say the applicant has a steady income that’s sufficient to service the loan) can be translated into “1s” and the negatives (let’s say, the applicant has diabetes) can be translated into “0”. Then the score can be summed up. The lender may set a minimum cut-off score and take a decision on whether to offer a mortgage, and on what terms.

There may be some questions, which are complete “deal-breakers”. For example, the applicant may have a very serious health problem. Or, the applicant may have been convicted for fraud, or some other serious crime. If one of those answers is a zero, the rest of the score will not matter. The mortgage will be refused. The entire score, in other words, collapses to zero.

This sort of string of ones and zeroes is known as a Boolean Function, named after the mathematician George Boole (1815-64) who first looked at such logical sequences in the 19th century. As anybody who has dealt with computers will know, the machines work in terms of ones and zeroes, with internal circuits (logic gates) being opened and shut on the basis of those numbers. Each zero or one in a string is one input, while the answer is the output.

Various Boolean functions may add up differently but the answer is always one (“the mortgage will be offered”) or zero (“the mortgage will be refused”). The “sensitivity” of a string as it is known depends on the deal breakers, if any, as well as on the total number of ones or zeroes required for the outputted answer to be either zero or one. 

This is a simple example of how understanding Boolean Functions matters in the real world. Everything a computer does, boils down to the use of Boolean logic. When you think of the number of things that are processed by computers, you get a sense of how important it is to understand how Boolean Functions work. 

Each function can have different rules obviously. For example, there can be a blanket rule where the output is a 1, if any of the inputs are 1. Or there can be a rule where the output is 1, if there are an even number of ones in the input. 
 

Mathematicians examine Boolean Functions in many ways. For instance, deal breakers are measured by the “sensitivity” of a Boolean function. If there are three deal breakers in that mortgage application, the sensitivity is three. 

There are other measures like “query complexity”, which tell the computer how many inputs are needed before an output may be produced. For example, an online health insurance form (or a doctor checking for symptoms) may start with a question about gender. The next question will vary depending on the first answer. There may be further variations in the following questions until the computer can calculate an output (or the doctor has a diagnosis). This is query complexity.

These values tend to be related — a computer scientist can usually judge what the value of one of these measures will be, for a given function, if the other measures are known. Usually one measure is the square, or the cube of another although other relationships are possible. 

However, “sensitivity” is an outlier. For the last 30-odd years, mathematicians have been looking for ways to relate sensitivity to other measures of Boolean Functions. There have been dozens of papers written on the subject of the sensitivity conjecture — that it is indeed related to other measures of Boolean Functions. 

Amazingly Hao Huang, a mathematician at Emory University, has just proved the sensitivity conjecture with an ingenious argument that looks at the way in which the points of a cube behave. The coordinates of the point of a cube can be represented by 000 (centre bottom), 001 (top front point), 010 (left bottom), 011 (left top), 111 (centre back top) etc. These inputs can be manipulated to colour the cube differently etc. Sensitivity is indeed related to other measures.

What is truly astonishing is that his proof is just two pages long and it was instantly accepted by the academic community. This breakthrough could lead to other results that help in the understanding of Boolean Functions.