A Chinese mathematician Hao Huang has solved a 30-year-old problem at the boundary between mathematics and computer science by using an innovative, elegant proof that has his colleagues marvelling at its simplicity.
Hao, an assistant professor of mathematics at Emory University in Atlanta, proved a mathematical idea called the sensitivity conjecture, which, in incredibly rough terms, makes a claim about how much you can change the input to a function without changing the output (this is its sensitivity).
In the decades since mathematicians first proposed the sensitivity conjecture (without proving it), theoretical computer scientists realised that it has huge implications for determining the most efficient ways to process information.
What’s remarkable about Hao’s proof, according to other experts in the field, isn’t just that Hao pulled it off, but also the elegant and straightforward way in which he did it. His proof hasn’t been officially peer-reviewed or published in any math journal. But soon after Hao put it online July 1, his colleagues quickly accepted it as fact.
“Whenever there’s an announcement like this,” University of Texas at Austin theoretical computer scientist Scott Aaronson wrote on his blog, “~99% of the time either the proof is wrong, or at any rate it’s way too complicated for outsiders to evaluate it quickly. This is one of the remaining 1% of cases. I’m rather confident that the proof is right. Why? Because I read and understood it. It took me about half an hour.”
Ryan O’Donnell, a computer science professor who studies number theory at Carnegie Mellon University in Pittsburgh, pointed out that Hao’s proof can be summed up in a single tweet:
Hao Huang@Emory:
Ex.1: ∃edge-signing of n-cube with 2^{n-1} eigs each of +/-sqrt(n)
Interlacing=>Any induced subgraph with >2^{n-1} vtcs has max eig >= sqrt(n)
Ex.2: In subgraph, max eig < = max valency, even with signs Hence [GL92] the Sensitivity Conj, s(f) >= sqrt(deg(f))
Hao is a tenure-track Assistant Professor in the Math and Computer Science Department at Emory University. After completing B.S. degree in School of Mathematical Sciences, Peking University back in 2007, he received the Ph.D degree in Jun, 2012, from Department of Mathematics, UCLA.
According to the information he posted on his homepage, Hao’s research interests include extremal combinatorics, probabilistic/algebraic methods, spectral graph theory, structural graph theory, and theoretical computer science.
*Adapted from a report by livescience.com
