The Sensitivity Conjecture has stood as one of the most important, and baffling, open problems in theoretical computer science for nearly three decades. It appears to have finally met its match through work by Hao Huang, an assistant professor of mathematics at Emory University.
Huang will present a proof of the Sensitivity Conjecture during the International Conference on Random Structures and Algorithms, set for Zurich, Switzerland, July 15 to 19.
“I’ve been attacking this problem off and on since 2012,” Huang says, “but the key idea emerged for me just about a week ago. I finally identified the right tool to solve it.”
The Sensitivity Conjecture relates to boolean data, which maps information into a true-false, or 1-0 binary. Boolean functions play an important role in complexity theory, as well in the design of circuits and chips for digital computers.
“In mathematics, a boolean function is one of the most basic discrete subjects—just like numbers, graphs or geometric shapes,” Huang explains.
There are many complexity measures of a boolean function, and almost all of them—including the decision-tree complexity, the certificate complexity, the randomized query complexity and many others—are known to be polynomially related. However, there is one unknown case, the so-called sensitivity of a boolean function, which measures how sensitive the function is when changing one input at a time.
In 1994, mathematicians Noam Nisan and Mario Szegedy proposed the Sensitivity Conjecture concerning this unknown case.
“Their conjecture says the sensitivity of a boolean function is also polynomially related to the other measures,” Huang says. “If true, then it would cease to be an outlier and it would join the rest of them.”
Huang developed an algebraic method for proving the conjecture. “I hope this method might also have some potential to be applied to other combinatorial and complexity problems important to computer science,” he says.
Mathematician to present a proof of the Sensitivity Conjecture (2019, July 10)
retrieved 14 July 2019
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no
part may be reproduced without the written permission. The content is provided for information purposes only.
- Jamaican students to participate in OECD survey – Jamaica Observer
- Women who don’t know how to cook don’t know mathematics – MP – GhanaWeb
- UC Irvine algorithm solves Rubik’s Cube in just 1 second – University of California
- Scientists create Ramanujan Machine: what’s it for, why name it after him? – The Indian Express
- Migrant students immersed in engineering – Foothills Sun Gazette
- How bad is the gender diversity crisis in AI research? Study analysing 1.5million arxiv papers says it’s “serious” – Packt Hub
- For the perfect martini, thank fluid mechanics – The Science Show – ABC News
- A mathematics whizz – Midrand Reporter
- Shakuntala Devi: Numero Uno in Math Wizardry – Hindustan Times
- US-settled siblings keen to teach Madurai students math for free – Times of India