Hao Huang (Mathematiker)

Hao Huang (chinesisch 黄皓, Pinyin Huáng Hào) i​st ein chinesischer Mathematiker.

Leben

Huang erhielt seinen Bachelor-Abschluss i​n Mathematik 2007 a​n der Universität Peking u​nd wurde 2012 a​n der University o​f California, Los Angeles, b​ei Benny Sudakov promoviert (Various problems i​n extremal combinatorics).[1] Er w​ar als Post-Doktorand a​m Institute f​or Advanced Study u​nd am DIMACS d​er Rutgers University s​owie am Institute o​f Mathematics a​nd its Applications d​er University o​f Minnesota. Er i​st Assistant Professor (mit tenure) a​n der Emory University.

Er befasst s​ich mit Kombinatorik (extremale Kombinatorik, Graphentheorie) u​nd theoretischer Informatik.

1992 formulierte Noam Nisan mit Mario Szegedy die Sensibilitäts-Vermutung für Boolesche Funktionen.[2] Die Sensibilität ist eines von mehreren Komplexitätsmaßen für Boolesche Funktionen und misst die Wahrscheinlichkeit, dass die Änderung des Wertes eines Input-Bits den Output ändert. Es gibt noch andere Komplexitätsmaße Boolescher Funktionen, zum Beispiel verschiedene Fragen-Komplexitäten (Query complexity), die messen aus wie vielen Input-Bits man den Output erraten kann. Bei den anderen Komplexitätsmaßen Boolescher Funktion war bekannt, dass sie in polynomialer Beziehung zueinander stehen, nur bei der Sensibilität war dies offen. Nisan und Szegedy vermuteten, dass auch die Sensitivität in polynomialer Beziehung mit den anderen Maßen stand. Die Vermutung war bis zu ihrer bejahenden Lösung 2019 durch Hao Huang eine der bedeutendsten ungelösten Probleme der Informatik.[3][4] Huangs Lösung war überraschend kurz und elegant und beruhte auf der Reduktion des Problems auf eine Aussage über Färbungen von Punkten auf einem Kubus in n Dimensionen (bei n Input-Bits). Craig Gotsman und Nati Linial hatten die Vermutung 1992 auf die Frage reduziert, ob bei jeder Menge M von Ecken eines n-dimensionalen Kubus, die mehr als die Hälfte der Ecken enthält, mindestens eine Ecke vorhanden ist, die mit vielen anderen Ecken von M verbunden ist. Bei nur der Hälfte der Ecken gibt es dagegen die Möglichkeit, dass die Punkte in M überhaupt nicht verbunden sind, wie man an einem Quadrat oder dreidimensionalen Kubus sieht. Huang bewies, dass es falls M mehr als die Hälfte der Ecken enthält einen Punkt auf dem n-Kubus gibt, der mit mindestens Punkten der Menge verbunden ist.

2019 erhielt e​r einen Career Award d​er National Science Foundation u​nd 2020 w​urde er Sloan Research Fellow.

Einzelnachweise
  1. Hao Huang im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
  2. Nisan, Szegedy On the Degree of Boolean Functions As Real Polynomials, Proc. of the Twenty-fourth Annual ACM Symposium on Theory of Computing. STOC '92, S. 462–467.
  3. Erica Klarreich, Decades-Old Computer Science Conjecture Solved in Two Pages, Quanta Magazine, 25. Juli 2019
  4. Hao Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Annals of Mathematics, Band 190, 2019, S. 949–955, Arxiv 2019
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.