Boole Function is the name that mathematicians and computer scientists give to any rule for turning binary data (Yes or No) into a binary result. A doctor, for example, uses this type of reasoning when deciding whether or not to prescribe a medication based on answers to questions such as “Are you diabetic?”, “Are you allergic?” etc. It’s a crucial concept in computing, because all computers do is compute Boolean functions.
The “sensitivity” of the Boolean function is the smallest number of changes to the data sufficient for the result to change. It is a measure of the complexity of the function. There are others, but they have been proven to give similar results: with the possible exception of sensitivity, they all agree on which Boolean functions are really complicated (exponential complexity) and which not so much (polynomial complexity).
In 1992, Noam Nisan (Israel) and Mario Szegedy (United States) conjectured that sensibility should also agree with the others, but for almost 30 years no one has been able to prove this fact. Until, in 2019, the young researcher Hao Huang, from Emory University, in the United States, surprised everyone with a solution.
Huang had been interested in the conjecture when he first heard about it in 2012, and he kept the challenge in mind as he worked on more accessible problems. Ten years earlier, Craig Gotsman (United States) and Nati Linial (Israel) had observed that to solve the problem it would be enough to prove a certain statement about vertices of cubes in many dimensions, but nobody knew how to do that either.
Until in 2018 Huang had the idea of using a mathematical result over 200 years old: the interconnection theorem by the Frenchman Augustine Cauchy. Excited by this approach, he decided to apply for a grant from the National Science Foundation to have the means to dedicate himself to the task. In an evening at the hotel, while writing the work plan for the scholarship, he realized how to turn the idea into a complete proof!
Best of all, Huang’s proof is barely two pages long (the entire work is six), is crystal clear, and opens up the prospect of proving other results.
The Hungarian mathematician Paul Erdös spoke of “The Book”, a work written by the deity (Erdös was an agnostic) which contains the perfect proofs of the most beautiful theorems. He would agree that Huang’s argument is “out of The Book”, the highest praise that can be paid to mathematical reasoning.
I have worked in the news industry for over 10 years and have been an author at News Bulletin 247 for the past 5 years. I mostly cover technology news and enjoy writing about the latest gadgets and devices. I am also a huge fan of music and enjoy attending live concerts whenever possible.
