Mario Szegedy
Mario Szegedy (* 23. Oktober 1960) ist ein US-amerikanischer Informatiker.
Szegedy wurde 1989 an der University of Chicago bei László Babai promoviert (Algebraic Methods in Lower Bounds for Computational Models). Als Post-Doc war er an der Hebräischen Universität in Jerusalem, an der Universität Chicago und den Bell Laboratories (1992), an denen er danach bis 1999 war. 1999 war er am Institute for Advanced Study. Er ist Professor für Informatik an der Rutgers University, an der er seit 2000 ist.
Szegedy beschäftigt sich mit Komplexitätstheorie, Kombinatorik, kombinatorischer Geometrie und Quanten-Informatik (er gründete QCteam, ein Quantum Computing Labor an der Rutgers University).
1992 formulierte er mit Noam Nisan die Sensibilitäts-Vermutung für Boolesche Funktionen.[1] 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. 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 – überraschend eleganten und kurzen – bejahenden Lösung 2019 durch Hao Huang eine der bedeutendsten ungelösten Probleme der Informatik.[2][3]
Er erhielt zweimal den Gödel-Preis, 2001 für seine Beteiligung am Beweis des PCP Theorems und 2005 für die Komplexitätsanalyse von Datenströmen. Für 2019 wurde ihm der Paris-Kanellakis-Preis zugesprochen.
Weblinks
Einzelnachweise
- 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.
- Erica Klarreich, Decades-Old Computer Science Conjecture Solved in Two Pages, Quanta Magazine, 25. Juli 2019.
- Hao Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Arxiv 2019.