Hao Huang (Mathematiker)

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

Leben

Huang erhielt seinen Bachelor-Abschluss in Mathematik 2007 an der Universität Peking und wurde 2012 an der University of California, Los Angeles, bei Benny Sudakov promoviert (Various problems in extremal combinatorics).[1] Er war als Post-Doktorand am Institute for Advanced Study und am DIMACS der Rutgers University sowie am Institute of Mathematics and its Applications der University of Minnesota. Er ist Assistant Professor (mit tenure) an der Emory University.

Er befasst sich mit Kombinatorik (extremale Kombinatorik, Graphentheorie) und 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 er einen Career Award der National Science Foundation und 2020 wurde 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. Additional terms may apply for the media files.