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.
- Picture this: ICERM program explores imagery of mathematics – Mirage News
- Guyanese students win top CAPE, CSEC awards – Stabroek News
- Science Hill student scores perfect 36 on ACT, looks to future in mathematics – Johnson City Press (subscription)
- Assistant Professor in Theoretical Particle Physics job with DURHAM UNIVERSITY | 183584 – Times Higher Education (THE)
- A math problem: How Delhi government is trying to get students to learn this subject better – The Indian Express
- CBSE Class 10 Mathematics-Basic Sample Question Paper 2020 with Solution – Jagran Josh
- Stock In The Spotlight :: PagSeguro Digital Ltd., (NYSE: PAGS) – Keep Reading
- Love Or Hate:: Clovis Oncology, Inc., (NASDAQ: CLVS) – Keep Reading
- Present Valuation:: New Residential Investment Corp., (NYSE: NRZ) – Keep Reading
- Shocking Alteration:: Workday, Inc., (NASDAQ: WDAY) – Keep Reading