By Carol Clark
A European heat wave provided the final spark Emory mathematician Hao Huang needed to crack one of the most important, and baffling, open problems in theoretical computer science.
Discover Magazine named Huang’s proof of the sensitivity conjecture one of the “Top 50 Science Stories that Matter” for 2019, due to the simplicity of the proof and the conjecture’s implications for processing information. And Popular Mechanics called Huang’s achievement one of “The 10 Biggest Math Breakthroughs” of the year.
Mathematicians and computer scientists had grappled with the sensitivity conjecture for three decades without success. Huang, an assistant professor of mathematics, became intrigued by it in 2012.
“I spent a lot of nights thinking about this problem,” Huang recalls, estimating that he pondered it off and on over the years for hundreds of hours. “I eventually became obsessed with it.”
In late June, Huang’s wife, Yao Yao, a mathematician at Georgia Tech, was an invited speaker at a conference in Madrid, Spain. Huang tagged along, with the idea that he would spend a few days sightseeing while his wife attended the meeting.
A heat wave swept through Europe, however, and Madrid temperatures reached 105 degrees. “I had to stay in my hotel, in an air-conditioned room,” Huang says.
During this forced confinement, Huang doubled down on the sensitivity conjecture. A key idea emerged. “I finally identified the right tool to solve it,” he says.
The sensitivity conjecture relates to Boolean data, which maps information in a true-false, or 1-0 binary. Boolean functions are one of the most basic of discrete subjects — like numbers, graphs or geometric shapes, Huang explains. Boolean functions also play an important role in complexity theory, as well as in the design of circuits and chips for computers.
There are many complexity measures of Boolean functions and almost all of them were known to be mathematically related. The only unknown case, the so-called sensitivity of a Boolean function, measures how sensitive the function is when changing one input at a time.
Mathematicians proposed the sensitivity conjecture in 1994 concerning this unknown case, but no one had been able to prove it.
Finally, sitting in a Madrid hotel room to escape the stifling heat, Huang came up with a simple algebraic method for proving the conjecture.
“I was quite excited,” Huang recalls. “And then I calmed down and started checking the work.”
His wife also checked the proof when she returned to the hotel from the conference.
Once he was convinced of its accuracy, Huang posted the work on his homepage.
Mathematicians and computer scientists from around the world lauded the proof. “Amazingly short and beautiful,” wrote Gil Kalai, a mathematician at the Hebrew University of Jerusalem. Claire Mathieu of the French National Center for Scientific Research described Huang’s proof as “a precious pearl” in Quanta Magazine.
The list of people who tried to solve the sensitivity conjecture and failed “is like a who’s who of discrete math and theoretical computer science,” Scott Aaronson, from the University of Texas, told Quanta.
Huang believes the method he developed may have the potential to be applied to other combinatorial and complexity problems important to computer science. He is happiest, however, about the crisp elegance of the work.
Often, he notes, mathematical proofs can go on for 100 pages or more and be too complex for all but the most specialized of readers to grasp. In contrast, Huang’s proof consists of two pages and every college level math major can understand it.
“Pure mathematicians are like poets and philosophers,” Huang says. “We’re not focused on whether our work has an immediate impact. We’re trying to get at larger truths, in the simplest way possible.”
It’s a completely different mindset from an engineer, he adds. “Engineers want to make things work, however possible,” he says. “Theoretical mathematicians want to understand how things work in their most natural way.”
A native of Shantou, a coastal city in southern China, Huang says his love of math emerged in his childhood. He attended a high school specialized in mathematics and later graduated from Peking University.
Many of his classmates went on to careers in technology or finance, but Huang prefers academia and its focus on pure math. “I love the flexibility of it,” he says. “All I need is a pen and paper. I can work on a train or in an airplane — or in a hotel room.”
Huang is not resting on his laurels following his proof of the sensitivity conjecture. “There are a lot of elegant theorems and beautiful conjectures out there that we don’t yet know how to prove,” he says.
Related:
Emory mathematician to present proof of the sensitivity conjecture
Mathematicians revive abandoned approach to the Riemann Hypothesis
No comments:
Post a Comment